There are at least two different ways to identify search engines. The most popular are "IP Delivery" and "User Agent Detection".
IP Delivery is done by keeping a list of the IP addresses of the search engine spiders. Your cloaking script compares the IP address of the visitor to the list of IP addresses of search engine spiders and if a match is found, it serves the optimized version of the page.
User Agent Detection is similar. A list is kept of the User Agent strings of search engine spiders. The User Agent string of the visitor is compared to this list, and if a match is found, the optimized version of the page is served.
IP Delivery is considered safer because an IP address is very difficult to spoof, while a User Agent string is very easy to spoof. A competitor could easily spoof a search engine spider's User Agent string to gain access to your optimized content.