by default caching attribute ignores the cookies!
you can set breakpoints in your controllers to see if output caching works or not, seems you know where to look! "... contains Cache-Control: max-age=0 but ..."
yes it is correct
and i suggest you to set Duration on the caching filter
look in the web.config file to see if the cacheControlMode attribute is not set to something strange! and if it is s-maxage=0 it is because of shared proxy
set the attribute like this on the controllers that you want to cache
[OutputCache( Duration = 360 )]