For small boards, it looks like the current trend is to use EagleCAD design tool (free version "EAGLE Light" adequate for Arduino shield-sized boards) which can create industry-standard Gerber RS-274x format files.http://www.cadsoft.de/freeware.htm
From there you can use one of the services that batch together boards to avoid the normally high setup fees.
As an example, the BatchPCB service offers 2 layer boards, 8/8 mil rules, at $2.50 per square inch with $10 setup fee. Average delivery in 3-4 weeks depending on volume of other orders.http://batchpcb.com/index.php/Faq
The PDX-Dorkbot PCB Group order may be the cheapest I've seen, at $5/square inch but you get 3 copies of the board, with no setup charge, and free shipping(!) 2 layer boards with 6/6 rules, soldermask both sides, silkscreen both sides. Eagle design rules available. They only do batches at intervals; the next one listed to go out 8am PST October 25th 2010.http://dorkbotpdx.org/wiki/pcb_order
Another alternative based in China, pricing in Euros, offering 14 or 10 business days for production. 0.2/0.2mm rules (8/8 mils). Online form for price quotes, 2 layer up to 10 layer PCBs.http://www.makepcb.com/
SeeedStudio does 6/6 rules, starting at $20 for a 5cm x 5cm board. You get 10 copies of the board (note, some may have shorts; 100% electrical testing extra $10.) Processed & shipped in 4-6 days. Complete order to delivery turnaround may be 14 days. Eagle format design rules available.http://www.seeedstudio.com/depot/fusion-pcb-2-layer-5cm5cm-max-10pcs-p-513.html?cPath=64_12
See also forum discussion: http://www.arduino.cc/cgi-bin/yabb2/YaBB.pl?num=1284352545
iTead Studio in China, $25 for 5x5 cm board, 10 copies. 6/6 mil design rules. Various shipping options. Reportedly they use the same fab house as SeeedStudio.http://iteadstudio.com