OK so this is what you will do:
1. Login to admin section.
2. Go to Promotions -> Shopping Cart Price Rules
3. Click on the “Add New Rule” button in the top right hand corner.
4. On the left is a set of tabs, In “Rule Information” set your general rule information.
5. In the “Conditions” tab you will need to do the following:
a. Click on the green + sign, a select box should appear. In the select box choose “Payment method”.
b. once select you should see something like “Payment Method is ...”, click on the “...”
c. a new select option should display, choose your payment method.
See screen shot for example of how it should look
6. In the “Actions” tab, set your desired actions.
Click thumbnail to see full-size image