Go to your local body shop supply/auto paint store and ask for 3M Weather Strip Adhesive - if I wasn't so lazy I'd go out to the shop and get the number off my tube. Bet you can't guess what it's made for. Yep, adhering weather strip.

Prepare the surface as described by leathermang - he's got the system. Then, follow the label instructions.

Dan