Houaiss dictionary (Lisbon, 2002) in entries bras-, brasil and especially brasil- has detailed information on this issue, which is broadly consistent with the other answers, but adds more information, crucially, on first known uses. So, complementing with other sources here it is.
The common name brasil
Before the Portuguese first arrived to Brazil the Portuguese common name brasil and related words in other languages denoted the reddish dye made from wood of the caesalpinia sappan tree, which grows in tropical Asia, wherefrom Europe sourced the stuff. When the Portuguese arrived in Brazil and found they could get the same dye from the related Brazilian caesalpinia echinata tree they named it pau-brasil (‘brazil wood’). See Paubrasilia in Wikipedia and this Italian dictionary (in Italian).
According to Houaiss (entry brasil-) the word is attested as brasil in Portuguese in 1377 and in Spanish and Catalan in the 13th century, and in the 12th century as brasile in Italian and brésil in French; the dominant view is that brasil derives from brasa―Portuguese, Spanish, Catalan, old Italian (now brace), and medieval Latin for ‘ember’―on account of its reddish colour. French Centre National de Ressources Textuelles et Lexicales (CNTRL) agrees: it says brésil comes from breze, old French (now braise) for ‘ember’ too. It has been suggested it could come from the Arabic wárs (‘curcuma’, a different plant family that includes turmeric) via a supposed adjective *warsi. Etymoline, adds that alternative old Italian name versino lends support to this hypothesis; but linguist Juan Corominas says this is semantically and phonetically problematic (Houaiss, brasil-). Off course, brasil could come from brasa, and versino from wárs.
Still according to CNTRL (braise) brasa is attested in medieval Latin from the 10th century (“brasas carbones”), but beyond that its origin is uncertain. The commonly advanced hypothesis is that it is perhaps of Germanic orgin. But the word is not attested in West Germanic languages, which would be the most likely source for medieval Latin. Similar words with related meanings are attested in Scandinavian languages though: Norwegian and Swedish bras ‘sparkling fire’, dialectical Norwegian and Swedish brasa ‘to roast’, and dialectical Danish brasa ‘to blaze’. But, CNTRL ads, a direct borrowing from Scandinavian languages into Latin is unlikely for geographical and chronological reasons; so the Germanic origin requires one to assume that a radical bras- also exited in West Germanic (Gothic) languages, even though it is not attested.
Monte Brasil and Brasil in old maps
Some maps from early 1300s onwards do indeed show an Atlantic island named Brasil or something similar. In this 1339 Angelino Dulcert map the name appears on an imaginary island off the west coast of Ireland (História dos Açores article in Portuguese Wikipédia says the name is Bracile, but I cannot see any e at the end of word). In various other 1300s maps, from 1351 on (see History of the Azores in Wikipedia) the name shifts to what roughly matches the Terceira island of the Azores. This was before the official (re)discovery of the Azores, which began in 1427.
“I. de brasil” appears again in the 1436 Andrea Bianco, a bit of which I show below. This map improves on the earlier ones, and the islands more closely resemble the Azores. I had to rotate that portion of the map some 60 degrees anticlockwise to get the alignment right though (same problem with earlier maps). “I. de brasil” is the easternmost island of the central group, as Terceira in the real world.
Bit of the 1436 Andrea Bianco map rotated some 60 degrees anticlockwise (names upside down in the original)
Then in this 1584 real map of the Azores, we have a “p. del Brazil”, a peninsula sticking out from the southern shore of Terceira. This is Monte Brasil; compare with today's map and pictures. Some maps from this time still show an imaginary Brasil island off the coast of Ireland too.
Clearly some names from the old maps were used to name the (re)discovered islands: “Corbomarinos” (literally ‘marine raven’; ‘cormorant’) island in the old maps matches Corvo (‘raven’) in the real Azores, and there is a “san jorji” island in the old maps, and a São Jorge in the real Azores. “Brasil” appears to have been demoted from an island to one of its peninsulas.
So as far as Portuguese language is concerned, what happened here is that a Portuguese, Spanish, and Catalan word was used in this series of maps. Why mapmakers, most of them Italian, chose this name is not certain. As discussed already in Seninha’s answer, it could come from the Irish family name Bressail (see article in Wikipedia) or it could be the common name brasil itself inspired by Pliny’s references to “purple islands” in the Atlantic, brasil dye being not of an altogether different colour (see Etymoline). It could also be some combination of both, old mapmakers creatively relying on all sort of sources for their maps.
Name of the country Brasil
There have been no end of hypotheses as to the origin of the proper name Brasil. Houaiss (entry brasil-) lists sixteen. It goes on to say though that the more recent studies and presentations of the issue give brasil the brazil wood tree as the origin of Brasil the name of the country. And really there can be no doubt about it. Here is Fernão Lopes de Castanheda (1500-59) writing on the issue in 1551, barely fifty years after the Portuguese first set foot on Brazil (História do Descobrimento e Conquista da Índia pelos Portugueses, vol. I, cap. 31):
Nesta terra mandou Pedralvares meter hũ padrão de pedra cõ hũa Cruz, & por isso lhe pos o nome terra de santa Cruz, & despois se perdeo este nome & lhe ficou ho do Brasil por amor do pao Brasil
João de Barros (1496-1570), writing one year later in 1552, says the same, regretting the loss of the name Terra de Sancta Cruz (Décadas da Ásia,, 1778 edition, Dec. I, Livro V, cap. II, p. 391):
per o qual nome Sancta Cruz foi aquella terra nomeada os primeiros annos […] daquella terra começou de vir o páo vermelho chamado Brazil, trabalhou que este nome ficasse na boca do povo, e que se perdesse o de Sancta Cruz
So it looks as though Brasil was the common name of the land from early on, and Terra de Santa Cruz was just an official name that did not catch on. The earliest known use of brasil in a toponym in connection with the country Brazil was in the 1502 Cantino Map, which shows a “Rio D Brasil” (‘river of Brazil’) near Porto Seguro (see Name of Brazil in Wikipedia). The name “R DE BRASI” is a lot clearer in this 1508 Johan Ruysh's map, about half way between the “circvluvs capricorni” and the “circvlvs aeqvinoctialis” (Tropic of Capricorn and the Equator). And in 1506-9 Duarte Pacheco Pereira already uses “terra do Brazil daleem do mar Ociano” to refer to the whole coast from, if his latitudes are correct, modern day Ceará all way down to Santa Catarina (Esmeraldo de Situ Orbis, liv. I, cap. 7, p. 16, 1892 edition)
Spelling matters: Brasil or Brazil
The word was originally spelled with and s. There was variation, but in other respects, not in the s. Houaiss attests both brasil and brasill in 1377. And in the diaries of Vasco da Gama expedition to India (1497-8) you find, referring to the dye, “brasill” and brasyll. But from the 16th century you start seeing the name both with s and z; you even find the two forms in same text. For instance, João de Barros has Brazil in the quote above, but “Brasil” here in the same book.
What happened was that old Portuguese, unlike now, had two voiced fricative consonant sounds, one represented by z, the other by intervocalic -s- (so coser ‘to sew’ and cozer ‘to cook by boiling’ were pronounced differently, see this question). But over time, starting in the 13th century in Lisbon and the Algarve, the two sounds merged into one. So you start seeing the same word, not just Brasil, spelled sometimes with s, sometimes with z. It was only in 1911 in Portugal and 1943 in Brazil that official spellings were approved that kept one version only, the one according to etymology, Brasil in our case. The main dictionaries from 1712 to the 20th centuries spelling reforms show Brasil only though. Curiously enough they show both brasa and braza, implicitly preferring the latter: in entry brasa they simply tell you to look up braza.