Although Picasa Web Albums have been searchable for a while now, the search box only appeared once you had logged in with your Google account.
However, Google have just added a search box to the login page, which you can choose to use instead of logging in. (You are automatically redirected to the login page if you visit picasaweb.google.com when you are not already logged in to a Google account).
There is unfortunately a major problem with this - the login page is a secure page (served up from www.google.com over https), but the action on the search takes you to an insecure page (plain http). In Firefox for example, using this form gives rise to a security warning popup, stating: "Although this page is encrypted, the information you have entered is to be sent over an unencrypted connection and could easily be read by a third party. Are you sure you want to continue sending this information?"
What can Google do to fix this? - I'd suggest that they turn the Picasa Web Albums home page into a straight search page, and do not automatically redirect non-logged in users to a the login page. Adding a login button to the page is the perfectly normal way to allow people who wish to login to do so. (This arrangement of a search box on the homepage, and a button to login is used for example by the Flickr homepage).
For the moment, you can perform the same search you get from the login page via the search box below - and since this page is served up over plain http, you won't hit the worrying security popup.