There are two issues here:
- What do we mean by collocation? And,
- Regardless of what we ultimately decide about 1., is there some relevant difference between cute puppy and strong tea?
Let me start with 2.
Cute puppy vs. strong tea
Yes, there is a difference, but I agree with Lambie (see his or her answer on this page) that the book you are using has misidentified it. Contrary to what your book says, and as many people have already pointed out, the meaning of strong tea is exactly the sum of its parts, just like in the case of cute puppy. That's not what's different about them. Rather, what's different about them is the following.
In the case of cute puppy, many different words aside from cute could be used to express an idea similar to cute puppy: adorable puppy, likeable puppy, delightful puppy, precious puppy, ... Cute may be the most popular word nowadays to use in this context, but there is nothing unnatural or strange about the other ones.
In contrast, in the case of strong tea, all plausible alternatives end up sounding awkward and unnatural: ?powerful tea, ?concentrated tea, ?intense tea, ... Mind you, if someone uses these alternatives, they will be understood. But then they are likely to be asked, 'You mean, strong tea?' Because when we want to say that a tea is powerful/concentrated/intense, the word we are supposed to use is strong. (See e.g. here.)
What is going on here is something similar to various other linguistic phenomena, such as set phrases, clichés (as Lambie mentioned in his or her answer), fixed expressions, and idioms, but it is not exactly any of those. Strong tea is not an idiom, because an idiom should have a figurative meaning, and strong tea does not. It is not a fixed expression, because a fixed expression should have 'a more specific meaning than the expression itself', whereas strong tea means exactly what it seems to mean, no more and no less. It is not a cliché, because a cliché is 'overused to the point of losing its original meaning or effect, even to the point of being trite or irritating', none of which applies to strong tea. And it is not a set phrase, because a set phrase 'is a phrase whose parts are fixed in a certain order, even if the phrase could be changed without harming the literal meaning.' After all, there is nothing strange about saying That tea is strong; in other words, strong can function both attributively and predicatively with tea. But that is not so with actual set phrases. We routinely say bad luck, but ?my lack is bad would be acceptable only under special circumstances.
It is only to be expected that linguists would seek out a name that would capture the special relationship between words like strong and tea. The name they have settled on is collocation.
Which brings us to question 1:
What do we mean by collocation?
I have found several scholarly sources that discuss the history and multiple senses of this term. Below I will use Seretan's Syntax-Based Collocation Extraction.
In short (pp. 13-14),
2.2.3 Collocation vs. Co-occurrence
As indicated in Section 2.2.1, the term collocation has originally been used in a broad sense, for describing the general event of recurrent word co-occurrence. This purely statistical view was later contrasted by a more restricted, linguistically motivated view, which explicitly states that the items in a collocation are syntactically related. The second view has recently gained in popularity, and some authors have suggested to use distinct terms to distinguish between the two understandings. More precisely, it has been proposed to use the term association or co-occurrence for the general statistical understanding, and to reserve the term collocation for the restricted understanding corresponding to the linguistically-motivated approach. For example, Manning and Schütze (1999) and Evert (2004b) state:
It is probably best to restrict the collocations to the narrower sense of grammatically bound elements and use the term association and co-occurrence for the more general phenomenon of words that are likely to be used in the same context (Manning and Schütze, 1999, 185)
In order to make a clear distinction between the two approaches to collocations,3 I refer to the distributional notion as cooccurrences (. . .) I reserve the term collocation for an intensionally defined concept (Evert, 2004b, 17).
The distinction between co-occurrences and collocations seems to be nowadays unanimously accepted (Bartsch, 2004), and will also be adopted in our work.
The above is preceded by five pages describing the history of the various meanings of collocation, and is followed by four pages explaining in more detail the meaning used in this work. Most of it can be read on google books, see the link I provided above.