There are one or two chronological things which I should like to clear up before proceeding here.
This graphic shows the geographical distribution of members of the genus homo over time:
Image courtesy of Wikipedia user Conquistador under the Creative Commons Attribution 2.5 Generic license.
It shows that homo sapiens never existed during the same period as homo erectus, and was only briefly in the same location as homo neanderthalensis. In fact, the former was active mainly in Asia, while the latter lived in Europe. I think it might be best to leave homo erectus out of it for the time being.
We also have to determine just when homo sapiens first developed gills. This is actually very important. If the gills appeared within the last 500,000 or so years, then
- homo neanderthalensis would not have had gills
- Other members of the genus homo could have expanded further
You did say that it is only a minor point as to whether or not other members of the genus homo had gills. I disagree only because that would influence just where these people (as I'll call them) could have gone. The Out-of-Africa theory says that homo sapiens (Not *all members of the genus homo) came out of Africa about 200,000 years ago. Other members of the genus homo may have already left. Here's a graphic of homo sapiens's travels:
Image courtesy of Wikipedia user Chronus under the Creative Commons Attribution-Share Alike 3.0 Unported license.
The dashed lines are important because they are hypothetical migrations - in other words, while there's evidence in the form of fossils for the others, there is not yet a lot of evidence for the dotted line migrations. If, say, homo neanderthalensis had gills, Neanderthals could have braved the trek from Scandinavia over the North Pole (not incredibly plausible, I'll admit) and to the Americas, thousands of years before homo sapiens got there via the Bering land bridge. That's quite important.
Okay, I'll get to the relevant part. You don't mind a timeline-esque approach to this, do you? I'll go with this format for now. Let's set a date for the gills of about 600,000 years ago.
600,000 years ago
Homo heidelbergensis is the species that first gets gills.$^1$ At this point, homo heidelbergensis lives in Africa, although it's about to venture outwards into the world. It soon does, and reaches southern Europe and western Asia with ease. In this world, though, it may be easier to cross bodies of water. With gills, homo heidelbergensis maybe able to go to many places before homo sapiens or homo neanderthalensis. It may be possible for them to quickly cross the Red Sea at a narrow point, thereby making the Arab world open. The Persian Gulf is also a little less scary, although I think that both bodies would only be crossable at narrow points, likely close to their origins.
300,000 years ago
Homo heidelbergensis has now ventured throughout eastern and central Europe. Crossing the Dardanelles or the Bosphorus was a lot less challenging, so more people can come through Turkey and into Europe. Around this point, homo neanderthalensis may be evolving from homo heidelbergensis. However, the latter could have pushed beyond the places that homo neanderthalensis may have gone in our world.
150,000 years ago
Homo neanderthalensis is in its prime. All of Europe may be open to it, including the British Isles (forget the Channel Tunnel!). Scandinavia is easy to get to, and islands near the Baltic Sea require no skill whatsoever. I won't go so far as to say that Iceland is a possibility (it isn't), but it's much easier to get through the northern parts of Scandinavia and Russia. At around this point, the North Pole crossing becomes an interesting idea.
Neanderthals would have had to get lucky to get across the North Pole, but they may have had some help. The Earth has entered the Wolstonian Stage, a glacial period stretching from about 350,000 years ago to 130,000 years ago.$^2$ This means that an intrepid group might have been able to make it up north. Any water along the way - which there probably would be - would be a trivial obstacle for the gilled explorers to reach.
100,000 years ago
Homo sapiens begins to arise back in Africa. The Red Sea crossing idea now holds for these people, and they will likely undergo that journey. They're starting a journey into Asia, which homo erectus has likely left (metaphorically, that is - they've died out).
Homo floresiensis arises. This peculiar species - believed by some to be a sub-group of homo sapiens - stands three and a half feet tall, and has a small brain size. There's a large debate going on as to whether or not these people were homo sapiens with a growth disorder or a unique species. Either way, we know that roughly 100,000 years ago, there are people - of one sort or another - in Indonesia.
The cool thing about Indonesia is that it's made up of many, many islands. I'd welcome the input of any and all Indonesians on this part, but - and this may be a justified theory - homo floresiensis may have been able to cross many years earlier. Well, the ancestors of homo floresiensis, at least. Gills permit swimming for extended periods; the extent of the periods depends on other characteristics of the creature. Still, it is fair to say that there may very well have been people on Indonesia before 100,000 years ago. It is thought that homo floresiensis may have reached Indonesia by boats. Gills mean that boats are unnecessary in some parts. Therefore, an earlier crossing is possible.
It may be a stretch, but I think it is certainly possible that these "hobbits" may now make their way into Australia. The outback is still as much a desert as ever, but Australia is by no means a wasteland. Homo floresiensis has quite a head start over everyone else.
For the next few sections, see this important graphic:
Image in the public domain.
50,000 years ago
In the world you and I live in, homo sapiens has by now spread throughout south-east and eastern Asia, and is venturing into Europe. The Neanderthals are doing just fine, and homo floresiensis is presumably surviving.
In this world, things are a bit different.
Homo sapiens will still reach Europe, much of Asia, and presumably Australia. However, they will find people already in Australia. Homo floresiensis may have developed quite the culture, and may put up some resistance to the newcomers. Yet if there are any physical confrontations, the "hobbits" are in trouble. Three and a half feet of a small-brained hominid isn't a lot against a human. Homo floresiensis will die out - possibly a bit later than in our Earth, but at some time, nonetheless.
35,000 years ago
Homo sapiens and homo neanderthalensis have met. Any speculative interbreeding is taking place, and the two cultures - if you can call them that - are interacting just as expected. In southern and central Europe - and northern Europe, to some extent - Neanderthals are starting to die out as they're replaced, even in Douglas Adams's stories.
But Neanderthals up north may have crossed during the Wolstonian glaciation, and made their way into Canada. Sure, homo sapiens is now dominant in Europe, Asia, Africa, and eventually Australia (homo floresiensis may have survived until 10,000-15,000 years ago), but the homo neanderthalensis has escaped.
20,000-25,000 years ago
Sometime around this period, some members of homo sapiens cross over from Siberia to North America via the Bering land bridge. I would suggest that an earlier expedition would have been possible, but that leads to the question of why it didn't happen earlier in our world, given that the land bridge presumably exited for many years before humans crossed it. In this world, the humans may or may not meet Neanderthals. The North Pole migration route would have required the Neanderthals to come over somewhere in central- to -eastern Canada. The ice sheets were still in place 50,000 years ago, and so Hudson Bay would not have been a challenge. Still, perhaps the coasts would have appealed to Neanderthals, so they could have started out on the Eastern end of North America.
It doesn't take long to travel from Alaska to Tierra del Fuego - perhaps only a few thousand years. If that's the case, Neanderthals may have already colonized all of the Americas. That's more than a little bit of a problem for homo sapiens, because, once again, they're the newcomers.
There are various ideas as to why Neanderthals died out. One could postulate that it was the mere appearance of homo sapiens that led to their decline, in which case, our group of humans will be just fine. If the deaths had to do with some geological event that was specific to a certain region, then the events here become uncertain. I'm hesitant to speculate about what will happen in this epic meeting, and so I don't think I'll go there. You can decide for yourself. But I think that the two cultures may coexist, at least for a while. If Neanderthals die out, it won't be for a long time. I suppose you could devote an entire question to the idea of homo sapiens and homo neanderthalensis coexisting.
Gills mean that homo heidelbergensis can reach much of Europe and western Asia easily, and they cover a lot of ground. Homo neanderthalensis quickly goes even further, going up to the northern reaches of Scandinavia. Homo floresiensis reaches Australia and gets along quite well until homo sapiens comes along. Homo neanderthalensis reaches North America but dies out in Europe, and homo sapiens conquers the globe, though coexisting with homo neanderthalensis in the Americas.
That was most likely not at all what you were looking for, so I'll try to devote a bit to the societal aspects of gills.
Fishing is big.
One of the issues with fishing is that it requires tools. tools didn't come about for some time (although obviously Neanderthals, homo sapiens and possibly homo heidelbergensis had them). If you don't have tools and want to fish, you have to use your hands, which is pretty hard.
Gills mean that you still have to sue your hands, but you can follow fish underwater. Have you ever seen someone (actually, Gollum might be a good example) try to catch a fish with their hands, miss, and stumble around in futility trying to get it? Gills mean you can follow the fish underwater. True, this is of no use in the shallows, but you can go into open water, which beats standing in a river looking like a fool with no fishing rod.
However, these are homo sapiens, and so have tools. Even something as unwieldy as a large stick can be helpful. Really, you just have to spear a fish, and if it's pointy enough, you're good. The problem comes when you want to catch bigger fish. You'll want to use your gills to your advantage, and the way to do that would be to go out into the open ocean - well, perhaps simply a bay - and go for something more like a swordfish. So you'll need something more than a simple spear.
In this case, you're not going to be able to just catch the fist (I've never tried to catch a swordfish, with or without a fishing rod, but it's definitely not easy). the best technique here might be to stab it until it dies. Perhaps you could use a tooth from, say, a shark and repeatedly whack it. Or maybe you just get a few pointy sticks and try to attack it with them. Either way, though, you'll have to realize that you can't catch the fish while it's still alive. The risk will be large, but the reward will be huge!
Escapes are easier.
I'm not a fan of swimming, and while I know that many people are, some animals aren't. Some large animals don't like water, and if those large animals are after you, you might have a place to hide! Let's say you have a creature like a cat (remember, a lot of cool creatures died out over the past tens of thousands of years) that's following you. It can climb trees and run really quickly . . . but it hates water. The way to get it off your tail would be to jump in a river/lake. Normally, you'd drown as it watched and waited. But with gills, you can stay there for a long time, and be just fine.
I'm guessing that the majority of the time you see a bridge, it's to carry people over a body of water. That's what the earliest bridges would have been for: To get people from point A to point B without having to swim. If you have gills, this isn't a problem anymore; you can swim for long distances. Well, I suppose "long" is a relative term, but you could probably get a good half mile without any problems whatsoever.
Carrying freight makes things a bit more interesting. Do you really want to carry an object that runs on electricity underwater? So there are two options:
- Build a bridge.
- Use underwater vehicles.
I think that the former is the better option, because underwater vehicles require storage, and if they're just used for crossing a body of water, they're not very economical.
$^1$ Homo heidelbergensis and homo rhodesiensis may very well be the same, so I suppose we can consider them as the same species, or possibly consider homo rhodesiensis as a continuation of homo heidelbergensis, if you want.
$^2$ I'm discounting the possibility of a crossing by homo heidelbergensis because they would have had to get to northern Europe for this to even be possible, and I doubt they would have had the time. They started dying out (in that form, giving rise to the Neanderthals) about 300,000 years ago.