What permissions should I give /var and /media?

In general all files should be 644 and all folders should be 755 and should be owned by the user your web server runs under. The mage executable should be given 550 permissions to allow execution.

This shell script should patch things up if run from your Mage root:

#!/bin/sh
find . -type f -exec chmod 644 {} \;
find . -type d -exec chmod 755 {} \;
chmod 550 mage

Source: http://www.magentocommerce.com/wiki/groups/227/resetting_file_permissions

I haven't see many mentions of using 700 and 600 but it is generally good advice. Unfortunately every server set up is different and needs to be weighed up against convenience (user access to update/edit files).

The underlying approach should be to only give away as little as possible and lock it down as much as you can (700/600 is good for this). In that respect the "official" advice on the wiki wants to apply to as many circumstances as possible and suggests read permissions for everyone (which means any compromised other service on the server will then for example be able to read app/etc/local.xml with your db configuration).

In your case it currently sounds like the files are owned by a different user than what your webserver/php process runs under. Changing the ownership of the files to the webserver should solve your original issue.

Please note that using 700 / 600 and assigning the files to the webserver means your normal user would not be able to edit the files.

The below I feel is a good compromise for convenience vs lock down. All files are owned by user:webservergroup

var and media 770 / 660
The server and your user is allowed to read and write from the var and media folders (session/cache/images).

the rest 750 / 640
Your user is able to edit/update the code.
The webserver is able to read the files for execution/display.

While Phil's solution is good I use a little bit different approach. In addition to making the "php/webserver user" owner of files I create additional group. Usually it's called dev. And I add "php user" and myself and other developers to that group dev. Then I do chgrp so that all files in Magento project subtree have group dev. I add +s bit to folders that ensures the newly created subfolders get the same permissions.

I've created a public gist with my fix_permissions.sh script. Feel free to use it:) It helps you to keep your whole Magento project subtree with good permissions.

https://gist.github.com/svenvarkel/8062778#file-fix_permissions-sh

The original question - var and media must have such permissions that "php user" can read and write to these folders. It must be able to write cache, session files etc under var and it must be able to write product image cache and images under media. So do as Phil advises: chown or chgrp these to "php user" and give rw permissions to "php user".

I think it's more correct to refer to "php user" in context of FPM (CGI). Webserver user can be different of that one that's running PHP.