Platform as a Service (PaaS) is one of the types of
cloud services that you can purchase.
Information Week produced an excellent buyers' guide evaluating different PaaS vendors and contrasting their offerings.
As contrasted with IaaS (Infrastructure as a Service), PaaS provides a in integrated programming platform. Usually this includes the underlying infrastructure layer, either directly from the PaaS vendor or from a partner.
The contrast with SaaS (Software as a Service) is that PaaS provides a level of transparency, configurability and programmability that is greater than SaaS provides. PaaS needs to provide a stable platform capable of running arbitrary customer code reliably.
As a practical matter, a PaaS vendor will need to offer only a limited number of Operating System/Database/Application Server/Web Server version combinations in their offering. This may result in increased vendor lock-in, since it may be difficult to match that stack even if the elements are industry standard (eg LAMP).
A differentiator between PaaS vendors who use the same stack may be an Integrated Development Environment (IDE). This may include things like a code versioning system, a test environment, libraries, or an online community.
Some PaaS vendors provide access to a proprietary platform. (One leading example is force.com.) These PaaS vendors are offering increased configuration capability over what would be offered from a straight-up SaaS vendor. Lock-in is a given for this type of vendor, since the customer's programming and configuration efforts will not be portable to another vendor.
As with any other sort of cloud vendor, make sure that security, auditing, and monitoring requirements will fit within your corporate standards. PaaS may allow you less flexibility for monitoring, especially performance monitoring, than IaaS will.
SLAs (Service Level Agreements) will almost certainly not provide penalties large enough to compensate for the real costs of any outage. Find out what the availability history is for the vendor candidates, and probe into the architecture underlying their offering to judge what the expected reliability will be. Then make sure that SLAs include penalties large enough that the vendor feels that they have skin the game when it comes to your uptime.