So what should be used:
Throw the ball up in the air.
Toss the ball in the air.
What should be used: throw up/toss?And should "in or into the air" be used ?
There are three variables here, for a total of nine possible sentences. I'm not going to write out all the permutations, so let's look at it with the alternative all in-line:
"Throw/Toss the ball [up] in/into the air"
You can have throw or toss, up included or not, and use in or into. These choices are all independent of one another, and you could use any combination of them, and all would be correct. The differences are all either stylistic, or provide shades of meaning.
A throw is usually a deliberate, purposeful act that is attempting to get something serious done. It implies a decent amount of force. A toss is a more casual action, you don't really mind exactly where the tossed thing goes, you're not putting any skill into, and probably not that much force into it. I hate to use an American example, but a baseball is thrown for a serious pitch, but if you're just putting the ball in the air to casually allow someone to hit it, it's a toss.
The optional up makes it clear that you want the person who is throwing/tossing the ball to mostly focus on it going upwards, not moving laterally. This is implied by the next part of the sentence, but not strongly. Without the 'up', some people will take that to mean it definitely has to get some height, but it can also go a long way laterally. If you want to emphasise that they should really put effort into getting it high way, you can add way in front of the 'up'.
"In the air" or "into the air" is largely stylistic. Some people will attach some shade of meaning to one that they don't attach to the other, but I'm not sure that would be consistent even within a single dialect.