(Copied from Dictionary.com)
Redundancy == Duplication or repetition of elements in electronic equipment to provide alternative functional channels in case of failure.
(Copied from Whatis.com)
Backbone == A backbone is a larger transmission line that carries data gathered from smaller lines that interconnect with it.
1) At the local level, a backbone is a line or set of lines that local area networks connect to for a wide area network connection or within a local area network to span distances efficiently (for example, between buildings).
2) On the Internet or other wide area network, a backbone is a set of paths that local or regional networks connect to for long-distance interconnection. The connection points are known as network nodes or telecommunication data switching exchanges (DSEs).
Hosts should be 'redundant' in many areas including hardware, data, connectivity, and even humans. To have "Redundancy" is to have duplication of everything you require; in case your primary service fails. If the host has "redundant connectivity" it means even if one bandwidth pipe fails the other is ready and waiting to take over. If server hardware fails they have other hardware waiting to be put to use, if a sysAdmin is hit by a bus they have another fully trained sysAdmin able to take his place, and if major data loss occurs there is a safe and recent backup available to restore it.
"Redundancy" can be equally referred to as "Backup" in some cases. One of the differences between "backup" and redundancy can be seen by the need for human intervention. A Redundant bandwidth pipe would mean you have more than one available for use and if one fails no human intervention is required to put the other one to use..it's all automated. Backup could mean it would require a human to "plug in" the other pipe and prep it for use when the primary one fails. In this case Redundancy is better than "Backup" since the redundant lines will quickly and flawlessly continue to work upon the failure of one. Having a "Backup" line may cause some downtime while the human works to put it into production.
The Backbone is usually the carrier(s) that the host uses to for it's connections. In extreme layman's terms your Internet Connection's 'backbone' from your home PC to the "World Wide Web" is your ISP and their "Backbone" provider may be Qwest, or UUnet, or sprint etc.. (the real backbones are Qwest et al where as the "ISP" is used here just as example to help clarify how it works).
When choosing a host, if price and uptime are not the most important factors, then redundancy and backbone providers should be important as they determine how well the host will perform during crisis. Things break everyday when it comes to technology. It's never a matter of "if" it will go down but rather "when". If you can handle a few hours, days, weeks, of downtime then I wouldn't worry too much about redundancy and/or backbones ..I'd concentrate on price instead.
If on the other hand downtime would cause you your own crisis then redundancy and backbones are vitally important! You'll want to find a host that is equipped to handle any number of problems and this means making sure they have a solid backbone provider as well as "Redundant Everything".
Disclaimer: There are differences between redundancy and backups however with such a general question I felt it may be easier to get the "general understanding" that many who are 'new to this whole thing' require...
I always assumed anyone who dared to even call themselves a host..even the really bad ones...had that covered. I never thought to ask *gasp* Could you imagine a host that didn't have a steady and redundant supply of coffee??????