Have finally cracked this one as Marius, I think. It does require a bit of luck though; if you get caught in too many unfortunate battles or key maneuvers don't work out, you will end up losing slowly but surely.
The key, as always, is to keep an eye on what matters - the VP. Rome is the main source, but you need to keep an eye on the Spanish VP location which gives you 3 victory points.
I've started leaning toward using the starting money to buy an African Legion and then waiting a turn before starting the African war. With a Roman subordinate leader and a Legion, it is relatively easy to steamroller the Numidians. Build the Numidian 50CV horsemen as soon as you can afford it - they're superb. Go for Cirta early, and then chase down and destroy the Numidian King. It takes time, but the single Legion is enough to do the job. With spare change, buy the second legion to speed up the job. Leave the new King there - he is useless elsewhere, but the two Legions + the good cavalry are useful in other theatres. The elephants and phalanxes are a waste of money.
In Spain, I run north. Depending on the movements of the Spanish major army, I would consider covering the the Spanish VP location for a few turns, but it is important NOT to get caught up in a losing battle. I tend to use the March money to buy up the second Spanish Legion. With two legions and a 2-star leader (Hadrianus tends to be my choice), you can pretty much keep the Spanish in check. Pounce on weak and isolated forces, recapture the VP location whenever the Spanish take it, and avoid getting caught in battles against superior forces. At some point, you should be able to spare 2 or more Legions from Italy - when that happens, send them over. Hadrianus with 4 Legions will crush the Spanish armies.
Both Africa and Spain are fairly sure things once you know what to do - unfortunately, it is what happens in Italy that will be decisive. And... no point in pretending otherwise; you're going to need some luck.
For an opening, I concentrate at Capua in the beginning and march everyone on Rome. Holding Rome is vital; both because it is the greatest source of victory points, but also because it lets you use proscription (money for more legions). Plunder the treasury and post an auxilia there to keep order - it's worth it. Once you have Rome, you want to try and wipe out the Sullan presence in Italy. Unfortunately, even with Marius and every unit available to you, the concentrated Sullan forces can wipe you out, so you need to be extremely careful. I'd avoid gambling on a major battle, and instead hunt down isolated legions with a massive stack of Legions and Socii. I also detach the Sicilian Legion in Italy, join it up with a Legate and the Auxiliaries from Africa (whom I usually send to Sardinia first, before going to Pisa), and send the Legate+Legion+Aux down to Malta to conquer that space as early as possible (it's 50+ very secure VP... it might make the difference between winning and losing). Sell prisoners as often as possible (I'd even prioritize this over Prison legions, I think. Try to get a few battles in Africa early - once you've slaughtered the Africans, you'll have lots of prisoners).
If Sulla does not return to Italy (I've seen this a couple of times), you should eventually be able to build up such a crushing superiority of Legions there that you can wipe out the Sullan forces and then take the fight to Greece. If Sulla does return (more often than not), the situation gets tricky. Despite the low CV of the three legions, Sulla when he returns will slaughter any force that you can muster (a small annoyance in the game - there is no good way to compare actual real combat strengths other than play experience). So you'll have to follow the classic strategy - be where he isn't. This is complicated, because there is little pattern to his movements (so accidental meeting engagements can easily happen), and you also need to take back Rome ASAP whenever it gets taken by the Sullans. A few fatal missteps in this part of the game will result in a loss.
Curiously enough, it actually seems easier to win this with Sulla in Italy. If he stays in Asia, the Optimates will be racking up huge numbers of VPs from Pontus, which is almost impossible for the Populares to match. In Italy, his VP harvest will be a lot smaller as the Optimates will lose the war in Asia and you are (hopefully) not allowing him to win battles that give him VP. Also - know which cities give Sulla VP - you want to take those, even if they don't give you VP also (e.g., Athens is usually an easy target). The contest basically is one of attrition. Avoid Sulla. Hit isolated Sullan Legions. And take back Rome. Once Fimbria is active, consider sending a couple of Legions to support him as he will usually be able to cause a lot of trouble and seize your two VP locations over there (though avoid major Sullan forces left over - they'll likely crush you).
Following that formula, I'm usually pushing 1800+ VP advantage by 84 BC with Spain and Africa pacified (watch out for the Sullan events generating new armies there), while Sulla is still around 1000. It's not a very satisfying way to win - crushing Sulla is nigh impossible, except with a huge amount of luck. One thing that did seem to work for me, though, was to trap Sulla in Sicily (i.e., occuppy Rhegium with your strongest force if he crosses over there). I think he would still have won if he assaulted me, but the AI was not willing to run the risk. So for the last 1 1/2 years of the scenario, Cinna occuppied Rhegium while Sulla and Pompeius ruled in Sicily and the odds and ends that I could spare from strait guarding duty tried to defeat the rest of the Optimates running around (not an easy task, when most battles require 3 or 4 to 1 odds). In either case, it is extremely hard to really destroy the Optimates, so just focus on containing them and running out the clock. Won the game with 2811 VP, more than double the Optimates. Only VP location I did not control was Syracuse (since Sulla was blocking that). Still only a "Minor Victory", though...
Apart from the fact that I'm still learning the game, what I'm finding frustrating is that it seems that I can either stop (if not totally put down) the Spanish rebellion, or concentrate on taking Rome and holding on in Italy, but not both. The best I've done so far was to transfer a few legions from Italy to Spain, and although I had the rebels on the run, Sulla made short work of me in Italy. 
