First, a few notes on simple ways to do this...
@ShadowKras gave a great simple answer with his necklace, assuming you can get the DM to change it to a belt slot.
@DuckTapeAl listed most of the normal means.
- Do note that Druids can cast a spell that is literally titled Air Breathing. 2 hr/level is a meh spell for this use, but in a pinch it can be worth it. Often I'll use this as a Contingency spell in case something happens that would make my companion suffocate.
- Land speed? Pft. Remember that a FLIGHT speed is often a more simple answer to the mobility problem.
- Don't forget that the Giant Octopus has a land speed, as do a few other primarily aquatic companions.
- Many companions are amphibious and superior to a shark anyway. Shark vs crocodile usually goes in favor of the croc when it comes to companion utility, just saying.
THE BEST WAY I KNOW TO TURN AN AQUATIC COMPANION INTO A LAND/VERSATILE ONE:
First, get an Aboleth Graft of Amphibious Skin (30,000 gp). It turns your aquatic companion into an Amphibian. The problem here is that Aboleth Grafts wither on most creatures after a few days. Not to fear! A solution is here!
Buy Dukar hand coral (CoV pg 64, 2600 gp) for you companion. This melds into them, so it's permanent, and grants regeneration abilities, boosted healing, and the boosted holding of breath. Per the text, withered Aboleth Grafts can be restored with regeneration. This means that your cheap piece of melded coral will keep your graft permanently in good shape! (If you don't want this for some bizarre reason, the Aboleth Mucus Sheath graft for 5,000 GP will also preserve your handy Amphibious Skin with a few bonuses).
If you companion doesn't natively have a land speed, there are many ways around this. Spells and items to grant flight are common and easy to get in both temporary and permanent forms. If you want the best permanency, again turn to Grafts. The following are the best, IMO:
- Climbing Legs (Illithid, 4,000 GP --- the best one, IMO: grants a 15 foot speed and spider-climbing effects)
- Feathered Wings (Fiendish, 10,000 GP --- great for a flight speed and attack, but the side-effects of fiendish grafts make them bad on companions generally)
- Rollers (Maug, 5,000 GP --- also great. They make riding hard, but give a handy trample attack which is useful on larger companions)
Now, the reason I tend to go with grafts for this is that they are as permanent as you can get. I tried the magic/item method once, and the DM hit me with an enemy that was using Disjunction and Antimagic...and my companion quickly suffocated and died. Not pleasant.
Reasons this works:
- Aboleths are creatures regularly found in certain places of the Material Plane. Flavor-wise there are many ways to get grafts from them due to this commonality.
- Illithids are also fairly common, making getting these grafts possible.
- Grafts are part of the creatures. Once there it's a permanent thing that allows you to defy the normal restrictions and worries that come with sustaining a creatures life and functions with magical stuff. They also allow better interaction with OTHER spells and buffs.
One Final Note:
Since you are a druid, the easiest way to make sure you can get Aboleth and Illithid grafts is to take the Aberration Wild Shape feat (which is awesome anyway) from Lords of Madness page 178.
With that said...
This isn't simple, but it is fun...
This is an unusual answer, but one I've found useful in some campaigns. Note: This answer is NOT intended to be the most simple route, because that has already been stated by other answers. This is intended to be the most interesting.
Ghostwalk (which did have a 3.5e update for the original 3.0 text) has an unusual spell called Ghost Companion:
The touched creature dies painlessly.
Instead of passing immediately beyond the Veil of Souls, the creature's soul remains on the Ethereal Plane and attempts to enter the Material Plane as a ghost. ... When the spell expires, the ghost creature dies the true death and its soul passes beyond the Veil of Souls.
It can be raised or resurrected before the spell duration expires.
What is unusual here is that last line -- "it can be raised or resurrected." Normally Raise Dead and Resurrection do not work on ghosts (which are undead), but this spell obviously precludes that to a certain degree.
Getting all the spells on the same list isn't particularly difficult with PF rules. The other two spells you'll need (Raise Dead: preferably the PF version | Restoration: preferably also PF version) are both cleric spells from a domain/subdomain. Any method of gaining domain spells will work (Domain Icon from FoE, Domain Staff from CC, level dips in Contemplative, etc).
You'll have to be level 9 for this to be viable, but at that point this suddenly becomes extremely powerful.
Of note is that "Ghost Companion" is a days/level spell, which is what makes this work. Also note that Raise Dead has a days/level limit, which means the two will ALWAYS be in sync.
Pair these with as many CL boosters as you can for better durations.
Now, here's why this is worth the effort:
- Ghosts have perfect flight, making movement anywhere a moot point, but retain their previous speeds as well, meaning just in case you've still got those.
- Being Undead means that you don't need to worry about ANY life-sustenance issues
- The Ghost template is an LA +5 template you're applying to your companion essentially for free
- You can turn your animal beatstick into a negative level, ability draining, armor ignoring, damage defying monstrosity
- Depending on which types of Ghosts you use (I prefer Forgotten Realms ghosts due to their superior abilities), you gain many things that no feasible companion would EVER have
- They are literally killed, which means there is no Mordenkainen's Disjunction, Greater Dispel Magic, item destruction/loss, antimagic, or anything else that could end this.
- Per Ghost rules, all equipment they had can be retained and used so long as you keep it safe.
- Being incorporeal means that not only can it fly anywhere, but it can pass through barriers that would have restricted it before.
Demo: My personal preference is to use this on a Giant Squid with my druid. In addition to the normal collar qualities I like to use on it, I almost always give it an Amulet of Natural Attacks or Amulet of Mighty Fists. The Enchantment I use is Ghost Touch to retain its full melee power. I then turn it into a Ghost. Suddenly my companion has 10 stretchy reaching touch attacks that are inflicting its various touch-related powers on top of its normal damage.
Tossing this on an octopus also works great, no matter the size, because Ghosts, ofc, aren't really impacted much by size except in matters of reach and (and a few save DCs).
The pattern would work like this:
- Cast Ghost Companion
- At the end of the duration, have Ghost Companion, Raise Dead, and Restoration prepared
- Cast Raise Dead before the duration of "Ghost Companion" ends
- Cast Restoration on the creature to get it back up to speed
- Cast Ghost Companion again
- Repeat endlessly
- Laugh in the face of physical companions and their limitations.