When using the branch-and-bound algorithm to solve an Integer Programming (IP) problem, the entire enumeration tree doesn't need to be evaluated and that's where the speed-up is achieved.
Suppose the problem is binary (all variables can be 0 or 1).
Each level of the tree doubles the number of the nodes as the previous, meaning there are $2^n$ nodes if there are $n$ variables.
However in B&B, some branches of the tree can be pruned off, eliminating all of those solutions entirely. (Assuming a minimisation problem), if the lower bound of a branch is worse than the upper bound of another, then it can be pruned off, drastically reducing the number of potential solutions.
It seems necessary to have both the lower and upper bounds of each node in order to prune off branches. If one solves the integer relaxed IP problem, they obtain a lower bound.
How, exactly, does one determine at the upper bound?
Any feasible solution can give an upper bound and it is usually found using some heuristic. The better the heuristic the better the upper bound, and the more efficiently the branch and bound procedure will work. Problem-specific heuristic usually work best.
If a heuristic cannot find a feasible solution, the upper bound is infinite and the whole search tree much be enumerated until a feasible solution is found.