Mark Antony's family was among the more distinguished, and more ancient, families in the late Republican state. His father was praetor in 74 and received an extraordinary command against the pirates, a task which he proved to be somewhat incompetent at. Cicero's colleague in 63 was a Gaius Antonius, Mark Antony's uncle--Gaius Antonius had been a prominent Sullan and was generally a man of ill repute, but he was still holding political office as late as 42, when he was appointed censor. The most famous and important member of the Antonian line besides Mark Antony himself was his grandfather Marcus Antonius, who together with Lucius Licinius Crassus was considered the greatest Latin orator and rhetorician before Cicero. This grandfather triumphed as proconsul in 100 over the Cilicians, was consul in 99, censor in 97 (during which year he enrolled Italians as citizens), defended Aquillius and Norbanus, served as legate in the Social War, and, although originally a Marian, was murdered by Marius in 87 after he turned on him. Mark Antony had no problems with the stature of his family

Antony's appointment as Gabinius' praefectus equitum was not a decision that anybody but Gabinius made. Antony's youth was spent sort of bouncing around--Plutarch says that he left the city for Greece when he became disillusioned with Clodius, and the New Pauly suggests that his decision to join Caesar, which it suggests may have been mediated by Clodius, seems like something of an attempt at (yet another) fresh start. When Gabinius picked him up he was in Greece studying military matters and oratory--it is during this period that Plutarch says he adopted the Asiatic style. Plutarch says that Gabinius (who no doubt had known Antony during his consulship, as Gabinius and his colleague Piso had worked closely with Clodius) came to Antony and asked him to join his staff, but Antony refused to go as a private citizens. Eventually Gabinius offered him the position of praefectus equitum and Antony joined the expedition.

Military command in the Roman state did not work the way it does in any state currently existing. Magistrates (or more likely, and in this case, promagistrates) held imperium over their provinces, with all that that implied. Legally the state had no right to interfere with a magistrate's activities besides advising him through senatorial dispatches (which of course were very influential) unless he did something illegal--and even then you'd have to wait until his promagistracy was over and he laid down his imperium, unless you managed to pass a motion to get him recalled. Apart from a handful of tribunes who were elected to raise the proconsul's first four legions the senate and state as a whole was uninvolved in the administration of the magistrate's army. Magistrates therefore appointed their own staff--prefects like Antony in particular were always appointed by the magistrate in command, never elected. It was a high command, and one that shows remarkable trust in the abilities of a very young man (Antony was 26 in 57), but young men with political inclinations generally got themselves appointed to some magistrate's staff early on. Military service (originally ten years' worth, but apparently no more than a year by Caesar's day) was a requirement for election to the quaestorship, the first senatorial magistracy, so politically inclined young men generally got themselves a military tribunate by appointment or election (you could become military tribune either way, depending on whether the magistrate in charge raised additional legions or not). Cicero, for example, served under Pompey's father Strabo during the Social War for a year, before entering into his legal career and then running for the quaestorship. Presumably Gabinius' tribunate positions were all full, so the appointment as prefect is, while unusual, perhaps not inexplicable. Besides, Antony was surely recognized early on as a very talented young man, since everybody and his grandmother wanted Antony to work for him.

You'll notice that Plutarch mentions that Antony didn't want to join the expedition as a private citizen. Magistrates' staff did not all necessarily hold official titles. Provincial governorship carried with it military command, provincial administration, and the reality that you might be stuck out in the boonies for five years with nothing to do if things were quiet. Governors brought with them as many talented and capable people as they could, not just to fill official positions like military tribunates or administrators, but also in various advisory capacities or even as entertainment and company. An entire group of politicians were what Cicero calls viri militares--men who held political positions and ambitions, but to whom military command was their primary career, and to whom political magistracy was more a method of getting imperium than anything else. These viri militares find themselves serving quite frequently on the staff of other men while they're not holding positions with imperium themselves--Cicero brought a number of them with him as advisers when he went to Cilicia, including his rather militarily talented brother Quintus, who served him capably as legate as he had served Caesar earlier. These men might hold official positions as legates or prefects, or they might just be there as private advisers. Caesar, though not a vir militaris by any means, was possibly a private citizen during his first campaign under Thermus--he did not serve as military tribune until he returned to Rome, and Suetonius describes him simply as serving in contubernio, which just generally means on a governor's staff, but can be used either of those with official position (like legates) or of the unofficial advisers a governor surrounded himself with. Lots of people came to the provinces as private citizens within the retinues of governors, either because of friendship, desire for adventure or travel, or the desire for the extraordinary wealth that came with hanging around a provincial administrator. These people might not even have any advisory duties at all, but were just there--Catullus joined Memmius when he was propraetor in Bithynia, basically as entertainment, someone to talk to and have good conversation with while out on campaign. Antony, had he not been so obstinate in his refusal to join unless given an actual position, might well have found himself on Gabinius' staff as a private adviser