A so-called random vote is one made very early in the game with no serious reasoning given.
At the beginning of a game of Mafia, each Townie has precious little information about the setup. As a result, the first set of votes are made with either no reasoning or humorously flawed reasoning.
The purpose of random voting (and the so-called Random Voting Stage or RVS) is to spur the game into action by causing players to act in revealing ways. For instance, a wagon on someone may cause them to panic, or a player may become a bit overeager in wanting to put votes down on players, or a player may suggest a Policy Elimination on another one (with some players agreeing and some disagreeing), etc. In this way, events of significance can come about. The first time many players find something they seriously want to eliminate someone over, they will remark that their vote is "no longer random".
One common trope of the RVS is that scum players will vote for each other or otherwise start their distancing early. For some time, this was a commonly applied tell.
One criticism of the random voting stage is that the votes are meaningless and pressureless, as players do not tend to have any real attachment to their vote or wanting to eliminate the player being voted for. The solution to this is to up the stakes. It is not at all unheard of for a random vote wagon to reach an elimination, or for a Policy Elimination to occur with little to no discussion, and so forth. By raising or even possibly enforcing this possibility, the RVS can become more serious.
Note that truly random voting, as with the dice tag, is strictly frowned upon. A vote that is demonstrably random carries no motivation to be read into, and is completely informationless. This is not the intent of the "random voting stage".