What is the difference between Google App Engine and Google Compute Engine?
Basic difference is that Google App Engine (GAE) is a Platform as a Service (PaaS) whereas Google Compute Engine (GCE) is an Infrastructure as a Service (IaaS).
To run your application in GAE you just need to write your code and deploy it into GAE, no other headache. Since GAE is fully scalable, it will automatically acquire more instances in case the traffic goes higher and decrease the instances when traffic decreases. You will be charged for the resources you really use, I mean, you will be billed for the Instance-Hours, Transferred Data, Storage etc your app really used. But the restriction is, you can create your application in only Python, PHP, Java, NodeJS, .NET, Ruby and **Go.
On the other hand, GCE provides you full infrastructure in the form of Virtual Machine. You have complete control over those VMs' environment and runtime as you can write or install any program there. Actually GCE is the way to use Google Data Centers virtually. In GCE you have to manually configure your infrastructure to handle scalability by using Load Balancer.
Both GAE and GCE are part of Google Cloud Platform.
Update: In March 2014 Google announced a new service under App Engine named Managed Virtual Machine. Managed VMs offers app engine applications a bit more flexibility over app platform, CPU and memory options. Like GCE you can create a custom runtime environment in these VMs for app engine application. Actually Managed VMs of App Engine blurs the frontier between IAAS and PAAS to some extent.
To put it simply: compute engine gives you a server which you have full control/responsibility for. You have direct access to the operating system, and you install all the software that you want, which is usually a web server, database, etc...
In app engine you don't manage the operating system of any of the underlying software. You only upload code (Java, PHP, Python, or Go) and voila - it just runs...
App engine saves tons of headache, especially for inexperienced people but it has 2 significant drawbacks: 1. more expensive (but it does have a free quota which compute engine doesn't) 2. you have less control, thus certain things are just not possible, or only possible in one specific way (for example saving and writing files).
App Engine is a Platform-as-a-Service. It means that you simply deploy your code, and the platform does everything else for you. For example, if your app becomes very successful, App Engine will automatically create more instances to handle the increased volume.
Read more about App Engine
Compute Engine is an Infrastructure-as-a-Service. You have to create and configure your own virtual machine instances. It gives you more flexibility and generally costs much less than App Engine. The drawback is that you have to manage your app and virtual machines yourself.
Read more about Compute Engine
You can mix both App Engine and Compute Engine, if necessary. They both work well with the other parts of the Google Cloud Platform.
EDIT (May 2016):
One more important distinction: projects running on App Engine can scale down to zero instances if no requests are coming in. This is extremely useful at the development stage as you can go for weeks without going over the generous free quota of instance-hours. Flexible runtime (i.e. "managed VMs") require at least one instance to run constantly.
EDIT (April 2017):
Cloud Functions (currently in beta) is the next level up from App Engine in terms of abstraction - no instances! It allows developers to deploy bite-size pieces of code that execute in response to different events, which may include HTTP requests, changes in Cloud Storage, etc.
The biggest difference with App Engine is that functions are priced per 100 milliseconds, while App Engine's instances shut down only after 15 minutes of inactivity. Another advantage is that Cloud Functions execute immediately, while a call to App Engine may require a new instance - and cold-starting a new instance may take a few seconds or longer (depending on runtime and your code).
This makes Cloud Functions ideal for (a) rare calls - no need to keep an instance live just in case something happens, (b) rapidly changing loads where instances are often spinning and shutting down, and possibly more use cases.
Read more about Cloud Functions