Step 1:Get a Google Account. If you're on an android phone, you have to have a Google Account. It's the account you sign in to so you can use the phone, the app store, your email... basically everything. If you forget your username, simply open the Play Store and click on the menu. If your name and email don't show on the top, go into settings... it's in there somewhere.
If you use iPhone and don't use Gmail, YouTube, or any other Google services, click here and sign up for a Google Account. (It's not cheating on Siri, she'll understand. I swear).
Sign up for Google+ at http://plus.google.com. Google+ ( pronounced "Google plus") is Google's version of Facebook, but with way easier to control and understand privacy settings. If you don't like Google+, or Social Media at all, that's fine. After signing up, go into your settings here, and set up everything so only you can view your info and data.
Step 3:On your phone, download the Google+ app. Once downloaded, open the app and log in using your Google Account credentials. For Android users, you can use the Google Photos app instead and achieve the same results.
Step 4:Set up Automatic Backup per the instructions found here. I recommend uploading on WiFi only, and not as full size pictures. This gives you unlimited storage of both the pictures and videos you take yourself or download from any app.
Step 5:Click on "Back up all" in the Auto Backup menu. This will make sure everything on your phone is properly backed up. When running the first time I recommend doing this while at home when the phone is charging, like overnight. This could potentially take a long time, depending on how many pictures and videos it must check and upload.
Step 6:You may trust in technology, but I like to make sure everything backed up correctly, as well as neatly organize my pictures for easy access. To do this, I go to http://photos.google.com on my desktop while viewing my camera roll on my phone. On the desktop, I'll grab all the photos from a certain day, time, event, etc in the Auto Backup folder and move them into their own album (i.e. Christmas 2012 album, which contains everything from Christmas Eve through Christmas Day in 2012). Once that is done, I make note of how many pictures and videos are in the new album (very easy, it tells you right below the album name).
Next, I'll go on my phone and select every picture and video I can find that also fits into that category. When done, the number of selected items SHOULD match the number of items in the new Google Photos album. If it is, everything is fine to delete off my phone. If not, I start scanning and matching pictures visually until I find the omissions and fix them.
Now if you want to get really fancy, you can add other details to your Google Photos album such as dates, locations, and comments to your albums. Be careful tagging people in the pictures, cause if they are in your contact list it will send them an email every time you tag them in a picture, whether they themselves are on Google+ or not. I learned that lesson the hard way...
OTHER BACKUPSNow that you have a Google Account, and you're comfortable moving stuff from your phone to "the cloud", there are other services that Google offers. Google Calendar and Gmail Contacts are the biggest and the best. Personally, I moved all my contacts from my phone into my Gmail contact list. Now, my phone numbers, email addresses, home addresses, and other information follow me no matter where I go. Even when I change phones, my contacts list, calendar, and pictures automatically follow me. Take the old phone and either destroy it or restore it to factory settings, and you're safe. For Android users this is all easy, simply go into the phone's settings, select Sync Accounts, and check the appropriate boxes.
For Apple Users it's slightly different, but not terribly difficult. Set up Google Sync per the instructions found here, and you're done! If you upgrade to a new iPhone, simply repeat this process on the new device. Same thing with the old, either destroy it or restore it to factory settings before getting rid of it.
So now the question is, why are you NOT doing this?! Quit complaining the you "lost my contact info" on Facebook, asking everyone to text you and announce who they are. Now, it's virtually impossible to lose all that information. And you can actually access it and use it without having a degree in astro-physics... like you need when trying to understand Apple's iCloud.