Mandarin is undoubtedly the most popular language for foreigners to learn in Taiwan. However, if you are willing to put in a bit of time and effort you can also learn Hoklo Taiwanese. In Taiwan the language is frequently referred to as Taiwanese (台語 or 台灣話) and is also known as Hokkien, Hoklo (福佬) or Minnan language (閩南語). Linguistically speaking the Hoklo Taiwanese is similar to Minnan, the language of the southern part of Fujian Province in China. This is the part of China where most Taiwanese trace their ancestry back to. Closely related dialects are also spoken in other parts of China and ethnic Chinese communities of Southeast Asia.
I have found there are two major obstacles to learning Hoklo Taiwanese in Taiwan. The first is that in most situations communicating in Mandarin is adequate and it is easier to use Mandarin than try to make a fool of yourself speaking Hoklo. The other is most Taiwanese lack a technical understanding of the language. They cannot write it in romanised form or explain the grammar or pronunciation.
That said if you put in the time and effort you can learn the language. I think it is best if you can find an experienced teacher at some stage to give you some guidance. It is important to learn some kind of system of romanisation as a learning aid. POJ (Church Romanisation) is the most commonly used and I recommend learning it as it is the most widely used system (despite its faults).
The language has seven tones and a number of difficult sounds. Also the tones usually change when a word is placed in a sentence. There are rules for this though. There are also variations in the pronunciation of some words from place to place in Taiwan. It is worth noting some of these, but don't get too worried about it.
Some people complain that Taiwanese people will speak Hoklo when they want to say something they don't want you to hear. I find this happens sometimes, but people will also be very warm and enthusiastic about anyone making an effort to learn Hoklo Taiwanese.
Taiwanese language links