This is an answer that tries to do a summary of all other answers, and to add something new
Solution 1: Reconstruct it
When you did nothing to prevent it (or something went wrong with your prevention), you'll have to rewrite the sheet.
1.1 The player has lost his sheet
The advise is to rebuild it before the session. All players should help the guy who lost the sheet, to gain time (that will be used to play!) and as much details as possible. Five/six brains are usually better than just one. Once the player has rebuilt his sheet, the party can resume playing.
Cons: If neither the party nor the player can remember the sheet (because it was a very advanced one, or it was their first time playing), the player should consider its rewriting from the beginning, following the same guidelines.
1.2 The player left it at home/college/whatever
If the player only left it at home, he could do a sheet rewrite on-the-fly. Whenever he needs to roll something, he tries to remember his bonus/malus. While this isn't very fair, the party won't have to wait the player to end up his sheet to play. You should consider it if you think you won't need sheets so much in the session. This sheet will be a temporary one, since the player still knows where his original one is.
Cons: Like I've said above, this isn't very fair.
1.3 You don't care and you forbid the player to play his PC to make him play an NPC instead
This is kind of a soft-punishment, that (hopefully) won't make the player leave the sheet at home again. Also, you don't lose time to rewrite the sheet before the session.
Cons: Is it really worth it? A player wants to play his character, not an NPC. He won't probably enjoy the session. Roleplay should be fun. Even if he leaves his sheet at home or loses it, you should help him in making a new one.
Solution 2: Online Saves
Probably the most advised solution. Since you already talked about it in your question, this shouldn't be a problem, but there are cases in which the party will not be able to connect to the Internet (f.e. sometimes we go play in an estate where there's no Internet connection. We still have our smartphones, but the connection speed there isn't very fast and we have no printer), so choose this option wisely.
So, what are the options for you to store your data online?
Players will place the sheet on their scanner and will send it to your email. This way you will always have a backup copy.
Cons: This whole procedure must be done every time. Plus, you should always delete the previous versions of the sheets to be sure you only store the up-to-date one.
2.2 Clouds (Dropbox, Google Drive, Onedrive...)
In the cloud-computing era, this is probably the most valuable option. Create a shared folder and store all the sheets there. If the sheets always have the same name (f.e. Vereos.pdf), the cloud will automatically replace them with the newer version.
Cons: You still have to scan the sheet everytime.
2.2.1 Electronic editable sheets
If you use such a sheet, you can avoid the cons and get 100% benefits from this! In fact, you will be able to edit it from your smartphone/tablet and then upload it to the cloud at the end of the session. If every player uses this method and they always download other players' updated sheets from the cloud, this is 99.999% safe, since the only way to don't play is that all the players leave their tablet/smartphone at home (if this is the case... are you sure you still want to roleplay?).
2.3 Website specific services (Obsidian Portal, D&D Insider...)
Some websites allow you to store your sheets and lots of other stuff. Even if sometimes the generated sheets are incomplete/inaccurate, this may be a good backup solution.
Cons: You have to access the portal everytime; Sometimes the sheets are not 100% accurate (inventory is missing, f.e.)
2.4 Social Networks
Just store your sheet on a Social Network. For example, Facebook allows you to store multiple versions of the documents, allowing you to rollback or see the changelogs from one version to another one.
Cons: Almost all the 2.1, 2.2 and 2.3.
Solution 3: Physical Data
You're not able to connect to the Internet: pens, pencils and paper are the only thing you can rely on. It happens more frequently than you may think.
One of the most popular advises: the GM always has a photocopy of the sheet to use when needed.
Cons: You must photocopy all the sheets everytime! Boooring! You have to cut out 5/10 minutes from every session (if you have issues with your scanner/printer, even 20 minutes). Plus, forests would not be that happy :(
3.2 GM (or a reliable player) holds the sheets
Use this one only when you know that the player (or the GM) is reliable and will never, ever, ever, leave the sheets at home. No forest-killing is needed, nor backup sheets.
Cons: Such reliable player does not exist. If he leaves the sheets at home, you can only switch playing Halo.
I went for this once. It's a very hard work but it eventually pays off. The GM holds a copy of the starting sheet of the players and then writes in a separate sheet of paper every change in order. This way you can always rebuild the sheets.
Cons: The GM should never forget to take note of every single change. This may be hard and overwhelming.
3.3.1 Shared Changelogs
In this variant, the GM is not the only person who writes out the changelogs. Everytime a change to a sheet is made, the player writes it down in a shared changelog sheet. This may help the GM since it's a very hard work if he's on his own.
Cons: Still, if the GM loses/leaves the changelog at home, this is just a waste of time and energies.
3.4 House as a holder
Who said that the sheet holder must be a person? If you always play in the same house, keep the sheets there. Just make sure you remember where you placed them, and keep them safe to avoid damages from wind, time, pets, moms, housekeepers, boyfriends/girlfriends, and so on.
Cons: One should remember to bring the sheets if for any reason the session won't be played there.