You can replace the logo within the theme folder on your server.

For example, if you use the subsilver theme, in phpBB2 it's in the template folder (phpBB2/templates/images/logo_phpBB2.gif). I beleive in phpBB, it's in themes.

Easy way, open your BB, right click the image, properties: check the path.
Right click image, save.
Make your logo the same dimensions (as Matt stated above) save it as the file name you just saved from the BB, now upload to the path you viewed.
Sometimes, there are 2 places the logo images are placed in phpBB - one in the images folder immediately inside the phpBB folder, and one in the themes folder... (phpBB/themes/NukeNews/images/logo.gif).
Make SURE you only replace the one in the themes folder first, then if you don't see the change, start hunting for another place it may be calling the image from.