On Debian, you'll have to install libhdf4-alt-dev (not libhd4-dev) and then re-compile gdal.
But there's a conflict with NETCDF if those drivers are enabled, so it's important to disable netcdf during the compile:
./configure --disable-netcdf --disable-fortran
And it should find the hdf4 libs automatically.
UPDATE
There was a recent post on the GDAL mailing list from Jose who posted some instructions on his blog to getting HDF4 support in GDAL 1.11.2 for anaconda:
wget http://repo.continuum.io/miniconda/Miniconda-latest-Linux-x86_64.sh bash ./Miniconda-latest-Linux-x86_64.sh export PATH=/opt/anaconda/bin:$PATH conda install numpy scipy matplotlib ipython ipython-notebook conda-build conda install scikit-learn pandas spyder numba numexpr cython binstar conda install -c https://conda.binstar.org/jgomezdans proj4 conda install -c https://conda.binstar.org/jgomezdans hdf4 conda install -c https://conda.binstar.org/jgomezdans gdal conda install geos
Reference: https://trac.osgeo.org/gdal/wiki/HDF
Reference: http://jgomezdans.github.io/new-version-of-gdal-packages-with-hdf-for-anaconda.html