This is, actually, a very nice question. The short answer is - no one knows for sure the origin of word аист. Though there are some facts that give us some hints:
- First evidence of using this word in Russian belongs to (most early) XV century.
- There is no evidence of this word in Proto-Slavic.
- There exists black (Ciconia nigra) and white (Ciconia ciconia) storks. On the territories populated by Russian language speakers there was no population of white storks before XIX-th century, so originally this word was used to refer black storks only.
- In Old Russian instead of
стеркъ had been used.
- Actually, no one knows for sure whether this words really indicated exactly storks, since the can be used for naming all long-leg birds.
As of 2013, anything else besides these fact is at least bit speculative. There are many different hypothesis, none of them is accepted by the majority of linguists. Here is an excellent overview of existing theories on this issue.
Let me conclude with this quote:
“Классическая” версия происхождения названия “аист” звучит так. Из
средневерхненемецкого диалекта было заимствовано слово “Heister”. Это
одно из старых местных названий сороки (Pica pica). Современное ее
наименование в немецком языке — “Elster”. “Heister” в польском языке
трансформировалось в “hajster”, "hajstra", затем перешло в украинский
и белорусский языки и некоторые диалекты русского в форме “гайстер”.
The theory mentioned above is indeed can be treated as the main candidate to be truthful. But be warned: though this overview is informative indeed, it mentions some fact that also are not 100% reliable. For example, mentioned word
лелека, even if it onomatopoeic (which is quite possible indeed, this is quite often case), hardly relates to any sumerian root. But, once again, no one really knows for sure in this case also :)