Don't use easy_install or pip, they don't really work very well for installing cx_Oracle since there are a number of environmental dependencies that the install scripts don't set up automatically. You need to get an oracle client driver, the quickest of which to find is the instantclient. Then point your ORACLE_HOME and PATH at the install location for the drivers, and install cx_Oracle itself. You should be good to go after that.
see: easy_install cx_Oracle (python package) on Windows
The question is about windows, but the answer includes info on *nix.