For those not in the know, if you are using the original OS (your default shipped home screen shows a lake, mountain at dawn/dusk, with time-lapse stars streaking across the sky), your orientation lock is the switch above the volume rocker.
for those whose default home screen is a glass pane with water droplets, your orientation lock is in the multitasking tray, accessible by following the steps given in the second post of this thread.
For those who are currently using 4.3 beta (you should know who you are.. Developers usually), you already know that your side switch is either a mute or lock, or you can use the multitask tray.
If you've unlocked your orientation, and your screen still doesn't rotate, you're holding it wrong.