Fluency is often confused with proficiency; it has even been an issue on this site. Simply put, proficiency is the level you have reached, whereas fluency is based on the automaticity and smoothness with which you can perform certain language tasks. (See also Fluency on the University of Oregon Center on Teaching and Learning website.)
For example, people with Broca's aphasia speak haltingly (i.e. not fluently), although they still retain their overall language proficiency.
Also, in 1974, E. Hatch ("Second language learning - universals" in: Working Papers on Bilingualism, 3) made a distinction between "data-gatherers" and "rule-formers". Data-gatherers tend to focus more on the development of fluency rather than accuracy, while rule-formers adopt a more analytic, rule-based approach. This can lead to differences in fluency between language learners who have the same overall proficiency level.
In order to avoid future confusion on this site, I would like the answers to this question to list the main types of fluency that are relevant to language learning, ideally based on authoritative sources (e.g. scientific literature).
Update: For the sake of this question, I will assume the following definition of fluency from Analysing Learner Language by Rod Ellis and Gary Barkhuizen (Oxford UP, 2005), which Scott Thornbury quotes on his blog:
the production of language in real time without undue pausing or hesitation