How would you start a network/security consulting business?

If you the typical security person, sales is not your strong suite. Heck, you may actually be very bad as a sales person. And since without sales you are not going to earn any money from this consultancy, you need someone who can actually close sales.

So what are you going to sell? Services? Do you have any software or other solution you will be offering? Go ahead, write them down in bullets. I know you know them, but you will be surprised when you try to boil each down into a soundbite. If you don't know this already, it is called an 'elevator pitch' because sometimes you will have a 10 or 20-second opportunity to make your case to a client, and that will not be the time to think up something clever to say. So know what you are selling, and know how to condense that to an elevator pitch.

Other things:
1. Now that you know what you are going to offer, and what your pitch is, get a good sales guy. Seriously. Your team may be extremely talented, but they need the contacts and they need the personality to 'close' sales. Not something techies are good at.
2. Create proposal, report and assessment templates (and get website/email/phones the usual logistics stuff)
3. More than one person? Think about the corporate structure. LLC, S-corp, C-corp? (Google for the differences and how each may effect you). Don't put this off--no matter how good friends you all are.
3. Land your first customer. Make sure s/he is willing to be a reference. Start looking for this customer now, even before the business is fully formed. The first customer is the hardest to get. Start by talking to people who are in a position to buy your offering. If you are currently working for someone else, you need to have a very clear idea about who is going to be your customer. Talk to every consulting firm, software company and VAR in your region.
4. Speak at places/seminars/conferences where potential customers show up. Stay longer and listen to them, talk to them, solve problems for them or give them pointers. People like nice people.
5. Did I say you need a sales person with a rolodex full of contacts that s/he already knows from previous jobs? You can hire someone on commission. Make a deal with a hardware sales-guy (so there is no conflict of interest)--when s/he visits a customer s/he can mention your company, make an introduction, etc.
6. Prepare for an initial dry spell. If the people can not handle no income, no health insurance, etc. for 6 months (just to be safe) then they are not ready for this. If you do hit the doldrums, look into opportunities for potential part-time contract work. It may sound strange, but this may help provide sustenance during lean periods. (for this, check out DICE, which lets you search for contract work based on W-2, corp-to-corp, etc). And don't forget, once you are at a contract gig, you are meeting a potential client who may hire your company for the next job.

Misc:
Any decent-sized clients will ask you about your workman's compensation, liability and errors/omissions insurance. This will set you back a few thousand dollars--talk to an insurance agent and find out.

Good luck.