OSH Park is a batch PCB service for 2- and 4-layer boards. They charge $5 / square inch, including shipping. They send you three copies of your board (or any other multiple of three). I don't know their minimum board sizes, but the smallest boards I've ordered were 60 cents. The turn-around time is about two weeks for me, with about two weeks for them to panelize, order, and receive the boards, and a day to ship (note: I currently live 20 minutes away from them, so this is probably more like 2.5 weeks normally). The quality is high enough, and the DRC rule limitations are acceptable, for hobbyist work. (Update 12/03/13: They seem to have reduced build time to 1 - 1.5 weeks!)

Because of how easy it is to order with them, this article is nearly redundant. Nevertheless, here's how I made these:

Note: This article has been updated Jan 1, 2017, with new details - Kicad has been updated, I've started using it on mac as well as linux, and Osh Park is as good as always.

The process to get boards made by Osh Park starts with the basics:

1. Learn KiCAD
2. Create a schematic
3. Create a board layout
4. Pass DRC with OSH Park's rules
5. Learn how to generate gerbers and a drill file

Now when you open up your Plot dialog, you should check the B. SilkS (back/bottom silkscreen), F. SilkS (front/top silkscreen), and Edge.Cuts (outline) gerber options. Your screen should look something like this:

And in the drill file screen, you should check Minimal Header box, and select Suppress Leading Zeroes from the 'Zeroes Format' selection, leading to a 2:4 precision. It should look like this:

Now click the Drill File button, close the drill dialog, hit the Plot button, and close that dialog as well.

Check your gerbers in gerbviewer (gerbv) to make sure everything is right. In the example below, I made sure that the vias looked right, the drills looked right, the stop-soldermask looked right on the top and bottom, the silkscreen looked right on the top and bottom, the copper looked right on the top and bottom, and that the dimensions looked right. A lot of checking!

Here's what mine looked like for a recent project I'll soon write about (front and back, respectively):

These gerbers were generated from a layout that looked like this (signal planes hidden):

Note that if you don't have any silkscreen on one of your layers, you shouldn't generate it at all, since I think Osh Park's site currently chokes on an empty gerber. Having said that, silkscreen is free, and if you have a completely empty layer, I suggest writing on it your name, the project name and revision, and the order date.

Also note that if your vias are too big, the tenting breaks. So if you want to tent your vias (meaning put soldermask over vias, which also lets you print over vias), keep the drills small! I use 12mil drills today; anything above 15mil will likely break and lose the tenting. This won't make your board not work, it'll just make your silkscreen uglier.

At this point, simply zip up your eight files: .gbl, .gbs, .gbo, .gbr, .gtl, .gts, .gto, and .drl. (Update Jan 1 2017: On a mac, there are seven .gbr files, and one or two .drl files. Osh Park accepts this just fine.)
Go to their home page, click 'Get Started Now', upload the zip file, give it a good title and name. Wait about 30 seconds for the server to process the files and generate renders/images of what your project will look like. Look over the renders (note that the back is mirrored so you can read the text, so to make sure everything lines up, mentally mirror it back). Then approve the project, and order whenever you're ready. I like to wait at least a day between approval and ordering to let things shake loose. Renders for this project look like:

Also, you can share your project with others. Then anyone building anything similar might use your board as inspiration.

Finally, do note that very small boards most likely cost you less than the cost of shipping alone, which Osh Park pays. So be a good person and don't order a bunch of little boards that they lose money on. If I order little boards, I either order several projects at once, or order more than 3 boards at a time. Current prices (October 2013) suggest the shipping is $1.32 for a small order, so keep it above $3-5! Otherwise this awesome service will not have money to make you any more prototypes!

Follow-up (3/17/2015): Looks like people are using this article! For example, this person writes more of their experiences you may find useful.