Like SQL*Server, you will want to install the database first.
If you use the SDE Direct Connect model, which is what ESRI recommends, then you have to install Oracle client software on the client machines (any machine which uses SDE).
In the case of ArcMap you have to install the 32 bit client because ArcMap is 32 bit. In the case of ArcGIS Server you have to install the 64 bit client because ArcGIS Server is 64 bit.
The easiest way to do this is to install the Oracle Instant Client which is available via Oracle or via the ESRI Customer Care Portal in the downloads section (see attachment). You can also install the full Oracle Client as well.