I've run a few products through FCC and CE testing, all including motor drivers (noisy) and USB ports (computer peripheral requirements for CE), running on multiple power supplies. Each failed a few tests at least a few times, typical price from start to finish from the testing facility (Austin, TX) was an average of $16k/device from first test to passing report. Not including our costs for travel or re-work.
Depends on a lot of factors: how big (reputable) the company doing the testing is, how big your device is, what voltages your devices runs on, what frequencies are on the board, number of I/O, number of configurations to test (to explain the last part, say your device can either run off USB or ethernet, you'll probably need to test both).
For something simple (clocks less than 200mhz), usually half a day of testing will cost between 1k and 2k I think. However, take these numbers with a grain of salt.
EDIT: they can also help you track down leaks and pass through testing the first time as well (i.e. say you're leaking tons of RF through a badly shielded ethernet port. They can track it down, and will have copper tape so you can test to see if a simple patch will fix it, which if the testing is much more expensive might be an acceptable step to add to your assembly procedure vs. doing a respin of the board).
Edit (after the first two replies below): I'm assuming a slow-clock device, say 20 MHz or less, as that's the limit of my PCB design skills anyway...