After reading the docs from ElasticSearch,
I found that if you're running on Ubuntu or Debian,
the package only ships with the OpenJDK because of licensing issues.
To fix this Java path problem, I installed the following
after installing ElasticSearch (as directed by the docs):
sudo add-apt-repository ppa:webupd8team/java
sudo apt-get update
sudo apt-get install oracle-java8-installer
java -version
Then upon running
sudo service elasticsearch start
everything worked and I had no more Java path issues.