For disaster recovery you should backup the Information Store as a minimum. Backing up the Mailboxes and Public folders as well gives you the option to restore just part of Exchange should someone delete something by mistake, but you shouldn't rely on it to enable to restore everything correctly if something goes wrong and you have to restore the entire system from scratch.
Yes, if you backup both the store and the folder it will take up twice as much space, as the same data is literally being backed up twice but in different ways. Also, if memory serves you need to ensure that you have turned on single instance backup, otherwise if any of your staff have large attachments which reside in multiple mailboxes, you'll end up backing up a copy of that file for every single user, rather than just one copy and that linking to the others.