I've read various wiki articles and guides on how to get through the activity, and playing a few routes, I noticed that the number of levels that a companion levels up each time seems to gradually decrease as his level increases. However, none of the guides I've looked at give me any idea of how many times I'll have to play this game to level up my companions. Does anyone know an approximate, ballpark number for how many trips it would take to get each tier of companion (easy, medium, hard) up to level 99?
In my experience, there are far too many factors that cause the partners' rates of growth to vary, including which path you decide to take, how many challenges you eventually face of each type, and how much work your partner ultimately does in combat. So, unfortunately, it's difficult to say for sure...
I remember getting one of the Easy companions from 1 to 99 after spending about 10 total hours on them, spread out over three days; if memory serves, I took only easy paths, and since I loaded them up with food beforehand, I pretty much sat back and let them do most of the fighting where possible, so they gained levels fairly quickly. Considering that the Medium and Hard partners are generally more fragile until they get over the hump (level 50 or so), I'd say you should probably expect to put 24-36 hours worth of cumulative gameplay into the Medium ones and at least 72 hours for the Hard ones if you follow the same strategy.
NOTE: When I say "cumulative gameplay", I mean time spent in-game, so don't rely strictly on my numbers; everything really depends on how YOU play the game, and the numbers I've given you are estimates based on my own experiences, so you may work faster or slower than I've detailed here.
One piece of advice: try to avoid burning out. Set some Trekking goals for a certain span of time, then do some other things once you reach that goal and come back to it after a short while. This is coming from a guy who has spent the last year working on 99 Smithing on non-members work (Level 94 at time of post), so you can believe me when I use the old adage: "everything in moderation".
If you have the correct equipment in your inventory for easy Trekking - it should take you no longer than a few days - providing this is the only thing you do on RS when you're logged in.
However, now with the introduction of EOC - this will take a bit longer. I would estimate around 2 weeks maximum.