I have a OCZ 256 SSD, I have removed my old drive, installed the SSD, booted up with a USB stick that has osx on it.
Now after I agreed to the terms, it is asking me choose where to install the OS, and the only drive that shows up is my USB.
I know I have to format the drive for the mac, how do I do that? Or was I suppose to do that BEFORE removing the old drive (I am suspecting YES), do I have any other option at this point or do I have to put the old one in again and format it first?
You skipped a few steps. Let me tell you how to proceed from where you are first. Then I'll tell you what I did and you may decide to do the same.
From where you are, boot from USB stick, then click Apple logo and run Disk Utility. Disk Utility should see your new SSD as unpartitioned space. Pick "partition" and then select 1 partition HFS+ Journaled. Before you hit apply, check options and make sure "GUID partition scheme" is selected. You may now proceed with the OSX install and now it should see the SSD as a possible destination. You are facing a rather lengthy restore from Time Machine or migration from Time Machine or whatever after the OS installs, which itself isn't exactly instantaneous.
What I think might have been easier is what I did:
1-Plug in your new SSD using a USB to SATA cable.
2-Use Disk Utility to create a single partition HFS+ Journaled, GUID partition scheme
3-Use CCC *(shareware $39, well worth it) to clone your existing drive, including the recovery partition (separate step) over to your new drive. This took 4 hours for 200 gig for me (completely unattended).
4-Hold down option while rebooting and boot from the SSD you just cloned.
5-If all is normal, THEN open up your Mac and put in the new SSD.
* CCC is carbon copy cloner. It was donationware until recently. You can use the trial version for 30 days without paying. This is more than enough time to install a new HDD. I opted to pay because though I don't use CCC that often, I do use it often enough to pay for it.