Process of solving a problem using ML
Going to your first question,


  What does "cleaning" the data consists of? How do you know if your
  data needs cleaning anyway?


Cleaning refers to the various processes to transform the data so that we can utilize it to the fullest. Removing unwanted features, incomplete entries, NaN or null values ( if the dataset is numeric ) consist of "cleaning" the data. This process is important because directly feeding the unclean data to the model may result in its stunted performance or runtime errors.

Once you have a large dataset, you need to transform it according to the problem which you are solving. If you are training a model to classify movie reviews as positive or negative then you can easily remove columns like "user_id", "category" etc. as these do not contribute to the polarity of the review.


  What features of the data determines which algorithm I should use? Or
  is it mostly trial and error?


Well, the algorithm you choose will mostly depend on your problem. Decision trees are good for smaller datasets and Deep Neural Networks ( DNN ) would be used to complex classification and regression problems.

Text classifier systems use embedding layers, TF-IDF vectorization, n-grams model. We basically choose a model on these factors :


Size of the dataset.
The complexity of the problem.
Computational resources ( in some cases ).


We can always play around with the hyperparameters and also modify the model so that it better fulfils our need.


  Are there any additional things that I should be doing other than
  trying different algorithms and testing how well they fit the data?


We choose a model based on the problem. CNNs have been prevalent in image-related problems. Word embeddings are useful in text classification. LSTMs are used in time-series-related problems. 

Tip: You can try to implement various algorithms from scratch ( without using scikit-learn or ML frameworks ). This helps you in developing an intuition regarding how the model learns from the data and makes predictions.