Execution plans are legacy. Execution plans are not as powerful or flexible as workflows, and cannot be designed using a graphical editor. Workflow is more flexible in comparison to Execution plans. Execution plans are strictly for task generation and ordering of those tasks. Execution plans are useful in some circumstances (for example, if you need to build your processes programmatically or through imports), but ServiceNow typically recommends using workflows for request fulfillment processes.
In the case of execution plan being assigned to a catalog item, the user sees each 'task' as a stage listed in the 'stage' column. Whereas with the workflow being assigned to the catalog item, the requestor only see's the workflow stages such as Approval, Fullfillment, Delivery, etc. In short, the execution plans seem more detailed.
Workflow hasn't replaced execution plans entirely, but its use is normally encouraged over execution plans because it also adds the ability to manage approvals, email notifications, rollbacks, etc. through the workflow mechanism.
