Depending on how 'in touch' with the language (in terms of understanding grammatical constructions and context clues) you may be considered fairly fluent with 80% or so character recognition
Think about your vocabulary in English. If you pick up a book with many words you don't know, you may still be able to comprehend it based on the context of the words that you might not know. Same applies for Chinese.
If you are interested in numbers and facts, here are the results of some studies:
Cumulative Character Frequency for the Top N Characters based on two studies (Huang 1994 and Da 2004)
Top 250 characters: 64.4% / 57.1%
Top 500 characters: 79.2 / 72.1%
Top 1000 characters: 91.1 / 86.2%
Top 1500 characters: 95.7 / 92.4%
Top 2000 characters: 97.9 / 95.6%
Top 3000 characters: 99.4 / 98.3%
The above table tells us that the top 1000 characters account for between 86% and 91% of the characters occurring in the real world. Assuming, with great hope, that there is a good correlation between the top 1000 characters found in these studies and the 1000 characters that most second year college students are supposed to master, we can conclude that there is a light at the end of the tunnel. Finally, while we wouldn't advocate studying characters solely based on their high frequency, we believe that studying such lists is a reasonable supplement to conventional study programs. Such lists also provide a sense of just where one is on the path to full Chinese literacy.
The results from the above studies have been used to generate two different sets of flashcards.
The Top 1000 Traditional Characters is based on C .H. Tsai's combined 1993–1994 data.
The Top 1000 Simplified Characters is based on Jun Da's combined classical and modern Chinese data, which has the advantage of being based on more recent data as well as more formal publications.
Source: http://www.yellowbridge.com/chinese/topchars.php