Greg Brown's book, The Savvy Flight Instructor, has some decent info on doing this. It's also useful for motivation, since as you correctly pointed out it's a tough road.
I started business as an independent instructor in September, so I'm still very much learning the ropes.
So far though, being a CFII has brought me the most business. Finding primary students is tough, mainly because they tend to walk into an FBO and say "I wanna learn how to fly" and they get pointed to the flight school there.
Instrument ratings are different. By that point, pilots know the lay of the land a little better and start asking around for instructors who they know are going to be around for a while. Plus, when doing an instrument rating you have some consistent income coming in.
And, aircraft owners will usually get a break on their insurance with an instrument rating. In some cases it'll be a substantial chunk of change and enough to justify the cost of the rating over a fairly short period of time. (As if being a safer, more proficient pilot wasn't enough.

)
Flight reviews are great, but you'll only bill maybe three hours so it takes a lot of flight reviews to equal a single instrument rating. On the other hand, a flight review is a good way to open the door to more business in the future.
Start a relationship with your FBO, or several FBOs. If they don't offer flight training they'll probably be happy to point students your way since they'll be buying fuel, supplies and maintenance work from the FBO.
Look at flying clubs in your area. They're a great source for business although you may need to join the club (which will at least give you an airplane in which to stay current.)
Half of my current students own their own airplanes, the other half fly through flying clubs. (It's not a huge sample size, but it's getting bigger every month.)
I've actually gotten some business through my website, so consider making a nice one.
I also get business through other instructors, so get to know them. Often they're either full or can't fly when a student wants to fly so they pass along those students to me. (Sometimes they just don't want to fly with the person because of their personality, so I get those referrals as well. It's a double-edged sword.

)
I just set up my business as a sole proprietor, which in Minnesota doesn't require any paperwork. You just hang out your shingle and have at it.
You might be able to form an LLC which could provide some protection but probably not. Also, in some states you need more than one person to form an LLC so if you're the only person, a sole proprietorship is probably the way to go.
Talk to a lawyer about which is the best way to go. Then write them a check. Keep the receipt because you should be able to deduct some costs related to setting up your business.
CFI insurance through AOPA probably isn't a bad idea. It should cover up to the deductible on your clients policy and offers some level of professional malpractice protection. (i.e. a former student crashes and their family sues you for not providing adequate training.)
Also, when instructing in an airplane owned by somebody else, consider requiring a waiver of subrogation from their insurer or at least being added as a named pilot on their policy. That should keep the company from coming after you if your student lands gear up or runs off the runway with you in the airplane.
Get familiar with the IRS Schedule C. Keep all your receipts, track your mileage going to and from lessons. I use Quicken to track my business income and expenses but I'll probably upgrade to QuickBooks this year, so consider just starting with QuickBooks.
You can probably deduct expenses related to staying current (night currency flights, instrument currency, etc...) and educational expenses that further your business (i.e., you're a CFI. You add on your CFII. The cost of obtaining your CFII can be deducted because you're furthering your business capabilities. I forget the exact wording.)
There was a decent article in Mentor, the National Association of Flight Instructors magazine, a few months back about tax issues for instructors. If you can dig up a copy it's worth a look. (I'm ambivalent on NAFI as a whole, by the way. For $39 a year I don't get a whole lot out of it.)
Get some nice, quality, business cards and instead of just saying "Joe Blow, Flight Instructor" list the services you offer on your card. i.e. "Flight Reviews, Instrument Ratings, Proficency Training, GPS Training, Primary Training, etc..."
It's a service business and you want to reinforce the message that you're there to provide a high-level of professional service.
My current students are my best advertising right now. They get to talking with other pilots and (hopefully) recommend me.
Being an independant is tough. You need to go out and find business instead of having it walk through the flight school door, but at least I get to keep everything I bill which can't be said for working at a flight school.