My company uses Bank of America Online Payroll. We are an S-Corp with no full-time employees other than the two founders/shareholders.
The Bank of America option is free if you are depositing directly to a BoA account. Being that both me and my business partner have BoA, this works for us.
The free version also allows you to file all the federal payroll tax forms, which is handy. It doesn't allow you to file the state payroll tax forms though, but if you live in NY (not sure about other states), you can do that all online directly through the states tax website.
You also need to remember to file with your state for unemployment insurance, which is a separate department from the tax department (at least in NY). And if you have other employees who aren't shareholders, you'll also need to register for workers comp insurance.
One trick I'll pass along -- with the disclaimer of talking to your accountant first -- is this:
If you need to minimize payroll costs, you can do some planning and pay yourself once per fiscal year, usually in Dec.
What you do is figure out what you think you need to make this year for a "reasonable salary" and pay that in one sum in Dec. The rest you can take as equity draws throughout the year, saving you the payroll processing expense each paycheck.
If you don't think you'll make enough to get a "reasonable salary", you can take your draws throughout the first 3 quarters, and then in the 4th quarter, try to have enough left in the back so that you pay yourself 1/2 of the total draws so far as payroll (Example: 18k yearly total > 12k over first 3 quarters, then final 6k through payroll in Q4).
This allows you to save some payroll processing costs, and make filing the forms easier -- it's just for one quarter, with the other 3 being zero-returns (which you still need to remember to do over the first 3 quarters).
But again, talk to your accountant.