You asked if you should get a provisional booking at the Registry Office (from this I assume that your gf is seeking a fiance visa). The answer is yes, it's always a good idea, but its evidential value is close to nil since it costs £35 and anybody can get one.
You asked about how to establish that your relationship is genuine. Since part of the rules for a fiance visa is proof that you met (and that means you met person-to-person in the physical, real-world) I assume that you have met. You will have some hard evidence of this including, passport stamps, hotel and meal receipts, and a few photos together. If you have visited together on multiple occasions, get that hard evidence also. The more the better.
Also, you will have (presumably) evidence of how you met on the net. If not, you will be able to explain it in a way that makes sense to them.
They don't want to see reams and reams of emails, and it can backfire if they read something and take it the wrong way. It can also slow the whole process down if somebody has to read through piles and piles of crap. Having a huge Skype log or similar can lead to the impression that you are addicted to cyber sex and the relationship is not physically subsisting. Be careful.
When I was doing casework for clients seeking a fiance visa, I would send the hard evidence I listed above along with a MAX of 3 photos, and 3 emails spaced out over the length of the relationship. I would include a cover letter that explained in detail how the couple met (doing this is critically important). If the couple had progressed to intimacy, I would explain when and where that took place. It's not a requirement, but it's an abrupt end to any questions about genuine relationship. Sham marriages and forced marriages do not have intimacy beforehand.
Adding...
If it's a US/UK relationship, they will not worry a lot about if the relationship is genuine or not. The approval rate for family path applicants from the USA is about 98%.