Pushing is a processing term. Generally you'd underexpose by 1-stop (which would give a negative that was 1-stop "thinner" or less dense if processed normally) and then push 1-stop to get a negative that had normal density (but more grain and contrast.)
Keep in mind that exposing is a separate thing from processing. You could expose normally and push or pull process, or you could adjust your exposure in different ways in conjunction with the processing. The lab just wants you to tell it whether it should be processed normal, or push or pull-processed, they don't care or know how you rated the stock or exposed it. Exposing is what you do, processing is what the lab does.
Roger Deakins, for example, in the daytime desert war flashback in "Courage Under Fire" overexposed the negative by 3-stops and then had the lab pull-process it by 2-stops, which means the final negative was 1-stop denser than normal.
"The Godfather" was shot on 100 ASA film rated at 250 ASA and pushed 1-stop, which means that since he rated it at 250 ASA instead of 200 ASA, it was still about a quarter stop "thin" or less dense than normal. However, Gordon Willis said he did not print back "up" to normal density, he left the image a quarter-stop dark, so in a sense it was not "underexposed" it was exposed correctly for the look and brightness he intended.
Truth is that it is common to not quite underexpose the stock as much as you are pushing it. In other words, if you ask the lab to push 500T by 1-stop, most cinematographers will rate it at 800 ASA instead of 1000 ASA, so they aren't quite underexposing it a full stop even though they are processing it to increase the density by a full stop. The reasons vary, it's partly that they don't want the graininess of 1000 ASA, but it's also because push-processing isn't always exact so giving yourself a little margin for error by leaning towards more exposure is not a bad idea. Plus few people are so perfect at making exposures that they are under a 1/3-stop range of error.
"Eyes Wide Shut" was shot on 500 ASA film pushed 2-stops but rated at 1600 ASA instead of 2000 ASA.
Gordon Willis used to say that there was no such thing as a 3-stop push-process, meaning that there wasn't much point, you weren't gaining 3-stops of speed.
The other problem is that let's say you shoot a test and decide that 2-stops underexposure looks decent but 2 1/2-stops underexposure looks bad -- that only leaves you with a 1/2-stop range to make a mistake, which is a narrow margin. When you work close to the edge, it doesn't take a lot to fall off the ledge.