Start with a simple algorithm that you can implement quickly. Implement it and test it on your cross-validation data.
Plot learning curves to decide if more data, more features, etc are likely to help.
Error analysis: manually examine the examples (in cross validation set) that your algorithm made errors on. To see if we can spot any systematic trend in what type of examples it is making errors on.