I like Tom's explanation, but here's another way to look at it:
Imagine you have a linear valve with a 1% deadband at 0% and you tell it to go to 50%. The valve moves and gets to 50.1% in 15s (well inside the 1% deadband). Now lets say you tell it to move to 75% and it moves to 74.9% in 7.5s. Now lets say you tell it to move back to 50%, it moves to 49.9%, but takes 8s to do it...
Now my personal definition (how I think about it) of deadband is the range the valve can be around 50% and still be satisfied or considered to be at 50% (ie, 49.5% - 50.5% is considered 50%).
The way I think of hysteresis is the time (or other factor) it takes for the valve to reverse direction; remember we had a linear valve that too 15s to go from 0% to 50% and 7.5s to go from 50% to 75%, but took 8s to go from 75% to 50%... That extra 0.5s is the time it took for the gears to move from one gear face to the other gear face taking up the little bit of slop in the gear train.
Please note that these are not dictionary definitions, but my way of thinking about these terms.