Name of Andalusia
The  toponym al-Andalus () is first attested in inscriptions on coins minted by the Umayyad rulers of Iberia, from ca. 715.

The etymology of the name has traditionally been derived from the name of the Vandals (who settled in Hispania in the 5th century). A number of proposals since the 1980s have contested this: Vallvé (1986) proposed derivation of the name from the Atlantic. Halm (1989) derives the name from a reconstructed Gothic term *landahlauts. Bossong (2002) suggests derivation from a pre-Roman substrate. Corriente (2008) suggests a derivation from Coptic *emendelēs, "southwest".

The Spanish form Andalucía was introduced  in the 13th century. The name was adopted in reference to those territories still under the Moorish rule at that time, and generally south of Castilla Nueva and Valencia, and corresponding with the former Roman province hitherto called Baetica in Latin sources. This was a Castilianization of Al-Andalusiya, the adjectival form of the Arabic word al-Andalus.

Vandal theory

The oldest theory has it that Andalusia derives from the name of the Vandals, the Germanic tribe which colonized parts of Iberia from 409 to 429.

That derivation goes back to the 13th-century De rebus Hispaniae. In the 14th century, Ibn Khaldun derived the name from al-Fandalus, the Vandals. Reinhart Dozy (1860) recognized the theory's shortcomings but still accepted it and suggested that geographically, it originally referred only to the harbour (Iulia Traducta, probably present-day Algeciras) from which the Vandals departed Iberia in 429 for North Africa, where they would establish the Vandal Kingdom (435–534). The first edition of the Encyclopaedia of Islam in 1913 adopted Dozy's view, and it became the mainstream account in 20th-century scholarship.

Werner Vycichl (1952) tried to put the Vandal theory on a firmer footing by suggesting that the form Wandalus, as used by the Berbers, was mistaken by Arabs for the Berber definite article w- and andalus, which with the Arabic definite article becomes al-Andalus.

Atlantic theory
Another proposal is that Andalus is an Arabic-language version of the name of the  Atlantic. This idea has recently been defended by  Vallvé (1986).

Vallvé writes:
Arabic texts offering the first mentions of the island of Al-Andalus and the sea of Al-Andalus become extraordinarily clear if we substitute this expressions with "Atlantis" or "Atlantic". The same can be said with reference to Hercules and the Amazons whose island, according to Arabic commentaries of these Greek and Latin legends, was located in jauf Al-Andalus—that is, to the north or interior of the Atlantic Ocean.

The Island of al-Andalus is mentioned in an anonymous Arabic chronicle of the conquest of Iberia composed two to three centuries after the fact. 
It is identified as the location of the landfall of the advance guard of the Moorish conquest of Iberia. The chronicle also says that "Island of al-Andalus" was subsequently renamed "Island of Tarifa". The preliminary conquest force of a few hundred, led by the Berber chief, Tarif abu Zura, seized the first bit of land they encountered after crossing the Strait of Gibraltar in 710. The main conquest force led by Tariq ibn Ziyad followed them a year later. The landfall, now known in Spain as either Punta Marroquí or Punta de Tarifa, is in fact the southern tip of an islet, presently known as Isla de Tarifa or Isla de las Palomas, just offshore of the Iberian mainland.

Gothic theory
Halm (1989) proposed a Gothic etymology.
Drawing attention to the term Gothica sors, a Latin exonym of the Visigothic Kingdom, which translates to "Gothic lot", Halm reconstructs a Gothic term that would correspond to the Latin term, meaning "lot lands", as *landahlauts. The hypothetical term would have given rise both to the Latin loan translation Gothica sors 
and to the Arabic al-Andalus, by phonetic imitation.

See also
Visigothic kingdom
Umayyad conquest of Hispania
Reconquista
Andalusia

References

Andalusia
Andalusia
Al-Andalus