Prior to my first gig I did the things suggested by everyone else, set up a lab, lots of reading, and took some training.
I had friend who had a worked for a company and they provide a nice little web site and community related to their industry. The community around his site was something that is line with my company's business so I joined. When I setup my account I put some funky characters in my name to see how it would be rendered and found that there was an XSS vulnerability. I promptly change my name to something normal and I let my developer friend know there was an issue.
They weren't totally sure of the risk but I informed him of XSS and its dangers. I told him that, among other things, XSS would allow me to steal his session cookie and interact with the site as him. I got the written go ahead from his company to do a POC (Proof of Concept) and hijacked his session. I send a message to me from him to show that I had been in. I promptly deleted my cookies and all such information.
There were intrigued with this and we had a phone conversation. They asked that I submit a proposal. I worked for a consulting business before so I had experience with proposals, but not of this nature. Off to google I went to research. I spend a lot of time making sure that I got everything down including the rules of engagement and get out of jail free card. At this point I didn't do insurance or the other legal stuff since it was rather informal (benefits of dealing with a smaller company). However, I do recommend getting legal paperwork in order to protect yourself and to make sure that everything is defined in writing.
After a few conversations and iterations of the proposal they hired me to do a test of the site and internet facing devices. I did it at a lower rate since this was going to be my first formal pen test outside of my day job. I just wanted to be able to add it to my resume and get some more experience. I slightly underbid on hours and spent extra hours to make sure it was the best I could possible do. I delivered the report to them with findings in the web app and their internet facing devices.
I made sure that the report was the best I could do. If you can't communicate the risk and mitigation strategies then the whole test is not going to be help to the business. All my internal experience had been with less formal reports. Getting this down was the one part I didn't practice. Seriously, who practices writing reports? I spent a lot of time researching report formats and such. After all that work I submitted the report. I spent three times as many hours on the project as I had bid, but I knew that going in. (BTW, bidding is a tough thing to get down, but I had experience with that. Rule of thumb take a guess, then double it.)
All in all they were very pleased. I got paid, had lots of fun, and have been able to leverage that into additional gigs.
Google took a while to find the relevant info but it was a great help. It will take lots of digging to find the relevant structure. Ultimately, the GPEN training from SANS was able to help validate my report structure, negotiation and the other non-technical portions. The class also gave me some additional tools to put under my belt. (I highly recommend it)
Sorry, but I can't post the proposal or report.
Hope that helps.