Why do we say stepped into a car with cars but can't say the same with planes? Instead we say stepped onto a plane.
Possibly because aviation language has a certain amount in common with maritime language, and we get onto a boat.
Scale often matters. One steps into a canoe or rowboat but onto a yacht or an ocean liner, into a car or van but onto a bus or train. Most of the aircraft most people board are large commercial airliners, not small private planes.
Mentioned this elsewhere, but it seems the controlling idea is whether the user normally sits or stands. If the user is "in" the boat, it is a small boat and the user is typically sitting. If "on" the boat, users are comfortable standing. The same applies to planes, buses,trains, automobiles, and elevators. For things that are straddled - fences, horses, bicycles, farm tractors - "on" is used.
I think your premise is faulty. I think either "into" or "onto" works just fine. Google Ngrams shows these results for the following phrases:
(No hits at all for "stepped into the airplane vs. stepped onto the airplane".)
That being said, I personally would use "onto the plane". I feel this is due to the relative size of the vehicle. If I were entering a small plane (like a two-seater) or a helicopter, I would use "into". In general, I think it's because of the feeling of being enclosed in the vehicle. So small vehicles, like cars and kayaks, get "into". Large vehicles, like commercial aircraft and cruise ships, get "onto". (I just noticed that @choster wrote the same thing in his own answer.)
Based on this answer on ELL.SE, I think these are the rules:
If the vehicle is boardable — you can be on board it — you're on it. Here, "on" is short for "on board".
This covers planes, trains, buses, boats, spaceships, and so on.
If the vehicle is too small to actually have an inside to get into, you're on it.
This covers bikes, skateboards, pogosticks, and so on.
In the remaining cases, you're in it.
This covers cars, canoes, and so on.
I think it's because, conceptually, the purpose of a plane or boat is to hold you up, where you would otherwise fall. Whereas a car or submarine is foremost simply containing you.