Installed shapely using pip, and had the same problem. So I went ahead and installed it like so:
sudo apt-get install libgeos-dev
And it worked. I'm running Ubuntu, so if you're on Fedora, you should run:
sudo yum install geos-devel
set the LD_LIBRARY_PATH, then run python
LD_LIBRARY_PATH
export LD_LIBRARY_PATH=/path_to/geos/lib:$LD_LIBRARY_PATHpython mytest.py
In ubuntu, the following commands should take care of it.It all goes down to the following packages.
(Original 2017)
sudo apt-get install libgeos-c1 libgeos-3.4.2
EDIT: (updated versions 2020)
sudo apt-get install libgeos-c1v5 libgeos-3.7.1