We know of the existence of storks in Middle-earth, but only from a passing reference by Bilbo, and so it's far from clear where in Middle-earth they were found. Since Bilbo knew of them, we can at least say that they were familiar to the Shire-hobbits, but that does not necessarily mean that storks were to be found in the Shire itself. The Shire's northerly location would likely make it too cold for storks - at least for varieties known in the modern world - so perhaps the Hobbits knew of them from the tales of travellers or storytellers who had passed through warmer, more southerly lands.

Though there are many different species of stork, few of these are seen in the parts of the world represented by northwestern Middle-earth. Bilbo probably had in mind the White Stork, Ciconia ciconia. This is by far the most commonly seen stork in Europe, though it rarely ranges as far north - at least in modern times - as the more temperate latitudes where the Shire was to be found.