ImportError: No module named gdal

There are two parts to GDAL: the GDAL utilities (gdalinfo, gdalwarp, etc.) and the GDAL Python Bindings (when you call from osgeo import gdal from within a Python script.). The two can be (or could be in the past) installed separately.

The fact that you "see" gdalwarp on the command line means that you have the location of the utilities on your PATH (environment variables). Some of the utilities are self-contained, some require the Python bindings (notably those that require calling a .py file). In order for the Python bindings to work, GDAL has to be on the PYTHONPATH environment variable.

Find the GDAL folder (will contain gdalwarp, for instance). Find the osgeo folder in Python's Lib/site-packages. Add both of these locations to PATH and PYTHONPATH. You should now be able to from osgeo import gdal in a fresh Python shell.

If you cannot, either you are missing some files in those locations (bad install), or you have not specified the path correctly / set the right environment variables. There's no other magic involved, it's either installed and linked correctly, or you did something wrong.

Note that for environment variables to be set and working, you need to "Apply/OK" the environement variables window(s), and also start a fresh command prompt / Python shell.