The first step to strong name an assembly is to sign it with a new key in the property pages under the “Signing” tab.

However, I had done this and still got the error. My mistake was that I had renamed my project, but had not removed the DLL that had been compiled previously. So, the WSP was trying to include that in its deployment. And that DLL wasn’t strongly named. Simply deleting it from the bin and obj folders and re-building the wsp fixed that.