Cylindrical aromatic compounds - fullerenes and hydrocarbons - are about to become highly interesting objects of chemical research. A tubulene (tubular benzenoid) is a hydrocarbon whose carbon skeleton is a hexagonal system embedded in a cylinder, with its dangling bonds at both ends saturated with hydrogen atoms. In this paper, elementary algorithms of low complexity are developed which allow the number K of Kekulé structures of an arbitrary tubulene to be calculated. For some particular classes of tubulenes - especially, for the classes of untwisted and fully twisted (normal) tubulenes - recurrence relations and explicit formulae for K are given and the asymptotic behavior of K is determined. Particularly remarkable is the fact that, in the theory of fully twisted tubulenes, quantities closely related to the Fibonacci numbers play an important role.