You could also set up a custom permission level out of the box.
- Navigate to your Site Collection (if you're in a subsite, you can go to Site Actions -> Site Settings -> Go to top level site settings)
- Site Actions -> Site Settings -> Advanced permissions
- Click Settings -> Permission Levels
- Click Add a permission level
I would recommend using the existing "Contribute" permission level as a guide and just uncheck the "Delete Items" list permission. Then, you can give your users that permission to the list.