The biggest difference, and this is huge, is that the criteria API allows you to think of your problem domain in terms of objects, not SQL.
If you want to play around with SQL type of syntax, then HQL is probably your best bet. It combines your object model with common query language constructs. But the Criteria API lets you think of your problem in terms of objects and their relationships at a Java level, and that's a HUGE difference.
Here's a good tutorial on the Criteria API, and how it works:
http://www.thebookonhibernate.com/HiberBookWeb/learn.jsp?tutorial=09howtousethecriteriaapi
And here's a good tutorial on using Hibernate3 HQL Hibernate Query Language:
http://www.ezhibernate.com/HiberBookWeb/learn.jsp?tutorial=08masteringhqlandnamedqueries
I think you'll find the Criteria API is very easy to work with once you start thinking about your data persistence problems in terms of your objects, which is really what Hibernate is all about.