What's the best way to automatically detect mobile vs. full screen devices and redirect to mobile site automatically? I'm concerned about SEO so it is safe to do a detection with PHP and redirect to mobile version without unwillingly sending Google to that mobile version?
If PHP is ok, what are good libraries to use?
You don't need any special libraries to do that. User-Agent header will do the trick.
It is good for usability to configure redirection to your mobile website.
The google webmaster blog has a very important topic on best practices for mobile sites, concerning redirection and duplicate content (!!!)
In my opinioun, a very comprehensive and up-to-date database (including source code in multilple languages) is WURLF: http://wurfl.sourceforge.net/