I get most of my piano sheet music from the internet, for free. The guitar players are probably in a even better position, with tablature for most pop songs, (and classical pieces too, I suppose) freely available. However, there is a fair share of free sheet music for the piano as well.
Because of the copyright laws, most sites do not contain material created later than the early 20th century. Finding modern pieces is a problem. However, there are plenty of public-domain classical (in the broad sense) pieces available. When searching for a piece you will probably want to visit several sheet music repositories before you turn to Google, which will give you heaps of trash to wade through.
If you are looking for a piece by a very famous composer, chances are that there is a dedicated site where you can download sheet music / recordings (e.g., www.chopinmusic.net, www.jsbach.org). You may want to look at such sites first, they are usually quite complete and the quality is good.
When I am looking for classical music, my first stop is usually the The Sheet Music Archive. The info page says that the site contains over 4000 pages of sheet music. It is a pity that it only allows two downloads per day (unless you are smart and guess the filename of the piece), but that is usually enough.
If you can read Russian, you might find Boris Tarakanov's Sheet Music Archive at notes.tarakanov.net very handy. I have only discovered it recently, but already found a few pieces which I had been looking for. You do not need to actually understand Russian to browse the site — an online translation service might work if you can't read text in Cyrillic.
mfiles.co.uk seems to have a little bit of everything. You can find various well-known pieces and some comments on them here. This site is nice to browse when you want are looking for new material.
It is sometimes helpful to hear a piece to decide if you like it before looking for the score. In other cases, you only know the composer and the melody, but not the name / number of the piece. kunstderfuge.com has an extensive collection of classical MIDI files. Of course, MP3s are more pleasant to the ear, but they are also harder to obtain and take much longer to download. MIDIs can usually give you the basic idea. Googling for MIDI files is easier than searching for free sheet music, but still a pain, so look here before you wander off.
Sibelius, the most popular notation software package, has a large repository of Sibelius scores on sibeliusmusic.com. You do not need to have Sibelius, but you will have to install Scorch (Windows and Mac only), a free browser plugin to view sheet music and play the pieces. Although all pieces on the site can be played and viewed for free, most (but not all) will cost a few dollars if you want to print them out. As this is a community site, there is also a lot of music here that is not worth your time, but there are quite a few gems to be discovered too.
If you are willing to pay money for the sheet music, the best sites are probably sheetmusicplus.com and virtualsheetmusic.com. This is just my impression however, as I have not used either of these services.
Finally, if you are after a relatively modern or rare piece, you might want to check out pianofiles.com. You will not find sheet music on the site itself, but it can provide you with e-mail addresses of people who have the piece you are after. You may then contact them by e-mail and ask politely to send the score to you. You might be asked for something in return. You can search the database anonymously, but the system will not show any e-mail addresses until you register. You can find a list of sheet music that I have on my member page.