[Crito]

"if Helium is used instead, assuming the Mars does have plenty of water."

I think you mean hydrogen? Assuming we can make a rover that can collect non-trivial amounts of water (say by baking it out of the dirt), we could make a hydrogen filled balloon with electrolysis.

[cygwin98]

Thanks. Fixed.