Good advice here. I haven't used KiCad yet, though this thread might finally spur me to try it. I've been using a super simple program called FreePCB for really simple analog stuff that can be routed by hand.
The thing that gets sent to the board fab is a set of files in "Gerber" format. So, the Gerbers are your last chance to confirm that the boards will be what you want. I suggest using a Gerber viewing program and look carefully at all of the files to make sure that they agree with your conception of what you expect the board to look like.
Finally, whatever fab house you choose, read all of their instructions and design rules, both to confirm that your board has a chance of being made, and because it's educational.
I've been happy with www.pcbfabrication.com for several runs of boards. I know people who go to a different house for every order, shopping around for the best price, but that just adds one more level of effort and worry for me. So I'm loyal to a good supplier.