Hannibals war elephants had already been in Spain for a considerable amount of time when he marched for Italy. Carthage had begun to employ war elephants of their own (most of the smaller North African variant and some Indian elephants bought from Syria), captured in Mauretania and Numidia, in the early third century BC, and first used them in 262 BC against the Romans in the battle of Agrigentum, where Polybios mentions 50 Elephants on the Carthaginian side (Diodor mentions 60). After the first Punic war and the Mercenary war, Hamilkar Barkas was sent to Spain with a force that included 70 Elephants. This was augmented by another 100 Elephants which arrived with his son-in-law Hasdrubal, after Hamilkar had already died. Hasdrubal thus commanded ~200 Elephants that he had with him in Spain.

It is not described (to my knowledge) how exactly Hamilkar and Hasdrubal got the Elephants over to Spain, but earlier military leaders had faced similar obstacles and overcame them.

Ptolemy II Philadelphos important Elephants for use in war from south of Egypt, and Eumedes, according to Strabo (XVI.769), founded the port of Ptolemais Theron (Ptolemais of the Hunt) somewhere on the African Coast of the southern Red Sea (the exact location is unknown), as well as several other landing places and hunting bases, down until the North Coast of Somalia at Cape Guardafui. From these places, the captured Elephants were sent by ship up the Red Sea to Berenice Troglodytica, another port founded by Ptolemy, and sent over land to the city of Koptos on the Nile, from where they could be shipped further North, probably up to Memphis where the chief stables were located. Elephants do not naturally fear water and are excellent swimmers, but getting them on boats in an orderly fashion would have required at least some training.

Ptolemy's naval architects designed a special type of ship for the transport of the elephants, the ἐλεφαντηγός or 'elephant-carrier', not galleys, but sailing ships with shallow draft - but this is owing more to the different nautical conditions in the Red Sea as compared to the mediterranean: The Red Sea is quite shallow, but has steady northerly winds most of the year, with southerly winds between October and May, without the periods of calms that afflict the Mediterranean. Oared ships, such as the Greek cavalry transports, also restrict the space available for transport (and elephants are large - eight horses take the place of 40 men on a ship, and Kistler estimates this much space for an elephant, not to mention the vertical space needed, though they probably were kept on deck). The journeys must have taken from a week minimum to as much as a month, depending on the distance of the port where they were captured, so it's certain that long sea-voyages with Elephants were possible. The crossing of the straits of Gibraltar, or from Africa to Sicily - or Sicily to Italy - would have taken a much shorter amount of time. Pyrrhus took Elephants to Italy with him as well, and he didn't use specially designed ships, but ships on loan by Antigonos Gonatas, so we can assume that they were nothing special. The Elephants were probably carried on deck, since, when some of Pyrrhus vessels were sunk in a storm off Italy, some of the animals managed to swim ashore on their own account and were collected by Pyrrhus together with some two thousand men and a few cavalry (although he lost about half of his Elephant force and arrived with only 20 out of 50). Kistler (p. 84) mentions an elephant, swept off deck by a gale off South Carolina in 1856, that managed to swim the remaining fifty(!) kilometers to shore on its own.

Another example for the carrying of Elephants over a short strait is seen with the Roman commander Metellus, who captured a large number of Carthaginian War Elephants at Panormus (our sources mention 100-140). According to Pliny (N.H. VIII.6, 16-17), he ferried them over the straits on rafts which were constructed by laying planks across barrels lashed together. Later authors like Zonaras embellished the story, writing that the planks were covered by soil and brushwork so that they gave the appearance of a farmyard, and the whole journey went so smooth that the Elephants never sensed that they were crossing the sea. In any case, this problem of transport doesn't seem to have been too big to overcome, and Metellus was able to lead the Elephants to Rome in triumph.

Thus it stands to reason that Hamilkar and later would have easily been able to transport Elephants across the straits of Gibraltar, as earlier Carthaginian leaders had already done to transport them to Sicily, relying on the transport capacities of the Carthaginian Navy.

When Hannibal set out towards Italy from Cartagena (Carthago Nova), he took with him only 37 Elephants, leaving 21 with Hasdrubal (his brother) in Spain, probably some of the original 200 had been sent back to Africa, while others would have died in the bitter fighting for Spain. The logistics must have indeed been daunting, elephants need around 200 kg of fodder each day, as well as vast amounts of water! This would have required a lot of capacity from the logistical train (Hannibals army included about 10.000 pack animals!), when the Elephants were not able to forage this amount daily. Logistical problems nonwithstanding, Hannibal averaged a speed of about 19 miles per day without losing any Elephants (Antigonos Monophtalmos had managed a forced march of 40 miles a day for one week across Asia a century earlier, but that had cost him several of his Elephants). The first major obstacle before the Alps was of an aquatic nature as well, the Rhône river, its further bank held by hostile Gallic tribes, with Scipio having already landed further south at Massilia.

Polybius reports the following about how Hannibal crossed the river which I quote here in full because it seems quite illustrative for the question at hand:

The way they got the elephants across was as follows. They built a number of very solid rafts and lashing two of these together fixed them very firmly into the earth at the point of entry into the river, their united width being about fifty feet. To these they attached others of the further side, prolonging the bridge out into the stream. They secured the side of it which faced the current by cables attached to the trees that grew on the bank [...] When they had made the whole bridge or pier of rafts about two hundred feet long they attachd to the end of it two particularly compact ones, very firmly fastened to each other, but so connected [...] that they could easily be cut. They attached to these several towing lines by which boats were to tow them [...] and thus were to convey the elephants which would be in them across. After this they piled up a quantity of earth on all the line of rafts, until the whole was on the same level and of the same appearance as the path on the shore. [...] As soon as [the elephants] set foot in the last rafts the ropes which held these fast to the others were cut, and the boats pulling taut, the towing lines rapidly tugged away from the pile of earth the elephants and the rafts on which they stood. Hereupon the animals becoming very alarmed at first turned around and ran about in all directions, but as they were shut in on all sides by the stream they finally grew afraid and were compelled to keep quiet. In this manner [...] they managed to get most of them over on these [rafts], but some were so frightened that they threw temselves into the river when halfway across. The mahouts of these were all drowned, but the elephants were saved, for owing to the power and length of their trunks they kept them above the water and breathed through them [...] most of them passing through the water on their feet. [Pol. III.45-46.]

In a pinch, as for Metellus, flat rafts were enough to get Elephants across smaller bodies of water, though not without dangers. Presumaly the Elephants weren't much accustomed to large rivers and their crossing after spending so much time in semiarid Spain. Here again we also have the motive of putting soil on the rafts to disguise their alien nature to the Elephants. Livy reports a bit colourfully that one mahout beating his Elephant led to a general stampede with many Elephants charging into the river, which led to their crossing. In any case, Hannibal got all his Elephants safely across the river. Supplying them with enough food across the Alps seems to have been a major problem for Hannibal, and after Polybios' account, he managed to get them across "in a wretched condition from hunger" [Pol. III.55].

In conclusio: Hannibals Elephants were already there, and they had been shipped across the straits of Gibraltar earlier by boat.

Sources:

• L. Casson, Ptolemy II and the Hunting of African Elephants, in Transact. Am. Phil. Soc. 123 (1993) 247-260.

• J. Kistler, War Elephants (Westport 2006).

• H. Scullard, The Elephant in the Greek and Roman World (Cambridge 1974).

If you are interested in War Elephants through all ages and nations, Kistlers book is an excellent work.