In halacha, it has to do with what parts of the tree/bush/plant in question the food grows on, and which is "renewed" on a regular basis (see linked source).
For halachic purposes, the tree is separated into 3 parts: the main stem or trunk, then branches that grow out of the main, and then the fruits which grow out of the branches. Different halachic views on whether a food will be a fruit or vegetable will depend on which part of the tree withers away during the winter months (if at all), and consequently when/where the fruit will fall off and regrow again.
For example, the accepted view is that only if the third part, the part where the fruit grows upon, is the one which regrows each time, whereas the rest of the tree remains standing the entire year, only then it is considered a fruit. So grapes grow on a vine, which has branches on which the grapes grow, while the rest of the vine remains throughout the entire year, thus rendering them fruits according to Halacha.
With bananas, however, the entire branch on which the bananas grow, withers away and regrows and therefore they are considered vegetables for these intents and purposes.
Of course the terms "fruit" and "vegetable" are relevant mostly for the sake of knowing which bracha/blessing to make on the said food. Does this hold significance in terms of bikkurim and the like, which you ask about? It would be interesting to look it up, but this should be a good starting point...
Source: Seder Birkot Hanehenin of the Alter Rebbe, chapter 6, sec. 6-7, who consequently mentions the various halachic views involved