There are two common free (as in beer) software choices. All are Mac/Linux/Windows supporting.
As of 2013, Eagle is more widespread in use, there is a much stronger library support available but KiCAD is catching up.
On the other hand, Eagle's free version is quite limited. 2 layers, 10cm by 8cm, 1 schematic sheet only, and non-commercial. They don't seem much in the beginning, but it's highly likely that you will hit at least 1 of them eventually (I have hit all of them in the same project except non-commercial), and will either have to pay or switch. KiCAD has no arbitrary restrictions, and is almost equally capable. Eagle added differential routing and delay matching and BGA fanout in v6 (not sure if they are in the free version), and that's the only thing I noticed that KiCAD doesn't have.
Lots of open hardware vendors use Eagle for their PCBs so there is an excellent range of libraries available. Some examples are
There is an excellent tutorial at Dangerous Prototypes about exporting gerber and drill files to send to a manufacturer. It is wise to use a gerber viewer to check the files before sending them off (there are lots, use google to find one).
This is how I work in Eagle. I am not a perfectionist, everything is a time tradeoff, near enough is good enough for me. This is what I do in Eagle
I generally follow a very similar process to Tom, with a few additions and differences: