The details of the Google Prediction API are on this page, but I am not able to find any details about the prediction algorithms running behind the API.
So far I have gathered that they let you provide your preprocessing steps in PMML format.
If you take a look over the specifications of PMML which you can find here you can see on the left menu what options you have (like ModelTree, NaiveBayes, Neural Nets and so on).
A variety of methods are available to the user. The support documentation gives walkthroughs and tips for when one or another model is most appropriate.
This page shows the following learning methods:
EDIT: I don't see any specific information about the algorithms, though. For example, does the tree model use information gain or gini index for splits?
Google does not publish the models they use, but they specifically do not support models from the PMML specification.
If you look closely at the documentation on this page, you will notice that the model selection within the schema is greyed out indicating that it is an unsupported feature of the schema.
The documentation does spell out that by default it will use a regression model for training data that has numeric answers, and an unspecified categorization model for training data that results in text based answers.
The Google Prediction API also supports hosted models (although only a few demo models are currently available), and models specified with a PMML transform. The documentation does contain an example of a model defined by a PMML transform. (There is also a note on that page stating that PMML ...Model elements are not supported).
The PMML standard that google partially supports is version 4.0.1.