Hello. I just installed Icy Phoenix on my website, and on the index, there is this block Search. So I want to change it saying "Search at Icy Phoenix" to something like "Search at BLABLA".

How is this possible?

You can do it by going to your index page, scroll down until you find "Edit this page" then look for the "Search block" and edit it.