SMS & Drafts: While you take backup, make sure you save drafts somewhere in text file or google keep or somewhere secure as they don’t appear after a restore. Also note that, If your phone is multi-sim there is fair chances you would lose sim information after restore. Check this with the backup software you are using.
Messaging (Hike, Whatsapp etc): Follow the basic guidelines of backing up and restoring messages from the apps. For Hike & WhatsApp, simply backup folder named hike & whatsapp after making sure you have backed up messages from settings. Otherwise, you’ll only be able to restore messages since last backup, and will lose message received/sent after it.
Call-logs: This usually goes unnoticed, But comes handy when you have some random one-time service provider you have been following up for a couple of days but don’t want to store their number as they are temporary providers.
there are several apps you can use on android for example: https://play.google.com/store/apps/details?id=com.idea.backup.smscontacts
Pictures, Videos, Audios: Pictures, videos & audios may be in various folder. Not all can be seen in gallery & media. Default Camera app and 3rd party apps may use different folders for that. Audios may be in recording folder also.
Bookmarks: If you are using chrome or Firefox are logged in with their sync account, bookmarks will be synced automatically. Other browsers must also be having option to export bookmark as html.
Manual Sync Apps: If some of your apps don’t support auto sync, you would need to do it manually. Eg: Study droid
Look & Feel: Take screen shots of home-screens in case u want the same look n feel after you restore. Nova launcher for android does a pretty decent job to restore the look and feel.
Apps: To restore/reinstall same set of apps make a note of apps you want to get back. Although these will be listed in your play-store/iTunes account, but the history will also include those you were not using anymore. Usually if you are switching phones with same vendor, it comes with apps to do that.
Set Date And Time: You must set date and time before you start restoring so that when you receive new messages, it will get stored out of order.
Although I tried to put as much as I could think of, I might have missed a point or two, and will keep updating it as and when I find out more things. But on a safer side, make sure you take care of things you want back.