An interesting question which can crop up in a CRM interview
Things to consider for choosing Microsoft Dynamics CRM Online
The answer which pops into my head instantly is CRM online doesn't allow to use custom workflows or call other DLL's from your plugins. I'm sure this the first thing which CRM developers will think of.
You cannot view the SQL database or do anything with it
great article on the limitations of CRM Online
One good point is CRM online rollups are automatically applied, so companies have to quickly regression test.
What hardware has the user currently got?
The big advantage of CRM Online is the customer doesn't need to buy any servers or software licenses. An on premise installation will need at least one server (assuming the customer has active directory setup) with SQL Server installed.
Users (e.g. how many)
CRM On premise uses active directory for the security authentication (CRM doesn't do the authenticating itself, it lets other software do it, a bit like CRM doesn't have any email capabilities but gets Outlook to do it).
If the company has a lot of users, this will mean a big process to migrate all these users to have windows live accounts, which are needed to use CRM online.
If you choose CRM, online then all your data will be stored in the cloud, on Microsoft's servers somewhere. Some companies do not want their data beyond their control like this which means CRM Online is not a viable option.
You also need to think about backups. CRM On premise will allow you to back up databases whenever you want, but because you do not have any access to the CRM Database or anything in the SQL Server you cannot backup your DB. If you needed to restore a database with CRM, online you need to liaise with Microsoft support and it's probably going to be a restore of a daily backup
There are some limitations to plugin development with online CRM because the plugins need to live in the sandbox (it breaks when the plugin tries to climb out of the sandbox). The plugins have to be one dll and cannot call any other dll's.
There is a limit of the number of workflows and entities you can with CRM Online. 200 workflows and 300 entities. As limits go this is pretty big and I have personally not seen a project which got near the limits. This limitation was true in CRM 2011, I assume it hasn't changed in CRM 2013 but I could be wrong.
For detailed list of the differences between CRM online and CRM on premise, these blogs offer a detailed description of the differences
Quick Compare: Microsoft Dynamics CRM Online vs. On Premise
Microsoft Dynamics CRM 2011 – Limitations of Dynamics CRM Online Vs On Premises
Picture from http://www.leafconsultancy.com