This first step is to install an operating system to your rpi. I'm a bit of a debian fanboy, and had an extra 2GB sdcard, so I went with a shrunk version of Wheezy. The image I used can be found here: http://raspberry.mythic-beasts.com/raspberry/images/raspbian/
For full instructions on installing an OS to your PI and other images, visit http://www.raspberrypi.org/downloads
On Ubuntu, I used gparted to format to fat32, and dd to write the img.
After you install the OS, plug in a usb keyboard and hook up the raspberry pi to a monitor. Assuming you are using Wheezy, on the first boot rasp-config will automatically run. You should use this tool to stretch the parition and enable ssh (under the advanced menu on newer versions I believe).
After I installed my img, I also removed the GUI to free up some space. (If you have a large SD, you can skip this.) To do this type these commands:
$ sudo apt-get remove --purge x11-common
$ sudo apt-get autoremove
This removes all packages that depend on X11 which is pretty much all of the GUI.