Mac OS X: You can search your iTunes library or the store, but to do so you have to click in the search box in order to type. There's no handy Command+F to get you there, but you can add one yourself with this useful Terminal trick.
Open up your terminal and paste in the following:
defaults write com.apple.iTunes NSUserKeyEquivalents -dict-add "Target Search Field" "@F"
Hit return, then relaunch iTunes. Now you can press Command+F to take yourself to the search field. If you'd prefer a different shortcut, just change the @F part of that Terminal code snippet to @ some other letter (or number). However you do it, you've now got a handy search shortcut in iTunes.