There are no invisible "video game" walls in an RPG, unless you put them there.
Doing so safely may not be an option for most characters; however, saftey wasn't the question.
Mid-air is counted as "unoccupied" for the purpose of determining whether or not you may move into a space.
To further illustrate this point, when you make a jump check, you have to jump into the air, and any character can most clearly jump off of a cliff at their own discretion. Inadvisable for most, but their own discretion is the only limiter in this case.
If you wanted to bull rush them INTO the BASE of the cliff, the answer is clearly "No", as the cliff base clearly occupies those squares.
Bull rushing them UP or DOWN the side of the cliff, while tricky, could theorhetically be possible, as you are pushing them into unoccupied squares on difficult terrain, but at some point the angle of slope would determine whether or not it would be possible, and/or require a climb check to complete if you have enough of a turn remaining to complete both actions.
As to the save, a previous answerer mentioned making a Climb check to save from falling. SevenSidedDice also pointed out the use of a Reflex Save, which more directly answers your question, as being appropriate.