For the beginners:
Creating a PCB is usually a process of two steps and LRR (lather, rinse, repeat). Step 1 is to create/edit a schematic (schematic capture). Step 2 is to turn the schematic, which symbolically defines a design, into a printed circuit board which defines the physical placement of electrical connections (layout). In this case, "gschem" is for schematic capture, and "pcb" is for layout. The purpose of the "schematic capture" is to draw a schematic, and in doing so, define a set of parts and a list of connections between these parts. Components are represented in the schematic by "symbols" and are represented in layout by "footprints." The combination of symbols and footprints is often referred to as a "package." The list of connections between components is called a "netlist".

I use gEDA and PCB preferentially for schematic entry and PCB layout.

The gEDA suite is a free Electronic Design Automation package featuring tools for schematic entry, and supporting a number of "friend" tools. It lives here: http://geda.seul.org/

PCB is a layout tool that can be used to make printed circuit board "artwork" (gerber files, etc). It plays nicely with gEDA, and lives here: http://pcb.sourceforge.net/

Why use this tool setup? It's free, it's effective, and it can do what I want it to do.

What are the drawbacks? These tools aren't as smoothly integrated together as professional schematic capture/layout programs. This is easily overcome if you're at all comfortable with shell scripts and Makefiles. If you're into GUIs you may find that the GUIs aren't as "pretty" as you might like.

Why might I be qualified to have an opinion? I've done schematic capture and layout successfully using Altium (protel), Cadence/Orcad, and Eagle, in addition to gEDA/PCB. I've successfully created thirty(ish) different board designs, and about a third of these were done with gEDA/PCB. In addition, I've worked with students and professionals lending assistance in the design of more than two-hundred different PCBs.

How I use the Tools:
I don't use the gEDA gui (if it even still exists), but instead I just call "gschem" directly. gEDA comes with a large library of parts, and more are frequently added. To be perfectly honest, I rarely use existing parts (unmodified) in ANY schematic capture tool, and I usually end up making my own. Consequently, Five Man has a big library of gEDA symbols/footprints that we're trying to get clean enough to publish.

Creating a component requires two things. First, you need a schematic symbol of the device. Second, you need a footprint for that device. In this case symbols belong to gschem, and footprints belong to PCB. gEDA defines on their website some "regulations" for symbol creation, which I recommend you read. Footprint creation is best described in a document by Stuart D. Brorson and Stephen Meier, found here: http://www.brorson.com/gEDA/land_patterns_20050129.pdf

The crash course:
1. Creating a symbol.
a. Is it something simple, or does something similar already exist? If you're creating something akin to a 7404, you could just add the 7404 to your design, then select the 7404 by clicking on it (it turns orange). Then right-click it, and choose "down symbol," which takes you into an editor. You can make your changes, an then "save-as" and save it as a new device in a personal directory somewhere.
b. Is it something "hard" or have a lot of pins? Use "tragesym" which has a tutorial here: http://www.geda.seul.org/docs/20040111/tutorials/tragesym/tragesym.html or out video at http://www.youtube.com/watch?v=G7nwSkiZwfg
Tragesym allows you to hand it a list of pin numbers, names, and orientations, and it will create the symbol for you. In practice, you'll probably need to edit the part a little, but it gets you really close.
c. Give all your symbols a "footprint" attribute, by using the add attribute feature when editing the symbol (this can be done on a per-instance basis in the schematic creation step). the attribute value should be the filename of the footprint you create in the next step.

2. Creating a footprint.
a. Does it exist? Most common parts already have footprints, or have a footprint "generator". PCB has two methods for footprints, macro libraries, and the "newlib" method of one file-per device... I haven't bothered to track what all is really going on with this, but I just keep a working directory of "known-good" footprints, which I've copied from pcb's newlib directory (/usr/share/pcb/newlib on my Gentoo machine), or which I've extracted from the macro library. On Gentoo, /usr/share/pcb has a script called "QueryLibrary.sh" and has a pcblib.contents file explaining the contetns of a library file (pcblib). To "extract" a SOD323 I can run "./QueryLibrary.sh pcblib SOD323 SOD323 SOD323 > ~/footprints/SOD323" in that directory and get the footrprint into a file.
b. Does it NOT exist? Create from scratch. Sorry. Read the "land patterns" document above. I create all my footprints with a text editor (vi) and then verify it by loading it up in PCB. Verify footprints by running "pcb" and then do File->Load element data to buffer then left click to place. Ctrl-m places a mark for measuring, which I use to verify footprints against the datasheet. Most footprints follow simple patterns, so it's a quick matter to text-edit even a massive footprint, but for brevity, I've written a bunch of perl scripts to make different footprints that I call. I'll try to get them posted at some point.

3. Schematic entry.
Load up gschem and "add components". "n" enters net-drawing mode, and "esc" leaves that mode. Note that "n" actually starts drawing a net immediately. When you're happy (or just ready to move on), name all your components using the naming tool "Attributes->autonumber text" which is used to give names to everything. Play with it a bit, and you'll quickly figure out how to replace all those "R?" with "R1" "R2" etc. Save and you're ready to rock.

4. Create the layout.
"gsch2pcb" is the program to create layouts from schematics. You can give it a whole list of schematics to use. I usually invoke it like this "gsch2pcb -f -d ../pcb/newlib/fp *.sch -o dev" which creates a layout using file elements instead of m4 libraries for footprints, searches my defined directory (../pcb/newlib/fp) for footprint files, uses all the schematics in the current directory, and spits out a .pcb file.

5. Place and route.
Open the file you created with pcb ("pcb dev.pcb" or whatever). Use "select->disperse all elements" do get all the parts in a place where you can see them. , and then move parts where you want them by click and drag. I recommend you click "window->key reference" and read the hot-sheet for things you can do. You'll need to load the netlist so that PCB knows how parts are interconnected, so you'll need to "file->load netlist file" and bear in mind that the netlist file will have been created by gsch2pcb with the name "dev.net" in my example above. Hitting "o" will draw and optimize the rats-nest that you're used to seeing in a layout tool. Play with the "line" tool to draw traces and connect nets. When you're done routing, PCB will give you a "Congratulations message". "file->export layout" to create gerber files.

Notes:
1. I keep symbols I create in my own folder structure. You can make the "add component" feature see such symbols by having a file called "gafrc" in your project directory with lines such as (component-library "../schem_parts/symbols") pointing at a symbol directory.

There's a lot of good information out there. I'll try to re-edit this to make it more detailed and to answer questions. Certainly, you should read the tutorials on PCB and gEDA's website also.