Funny you should ask that....
I just got up at 3 am to use my paper certificates to upgrade to first on a couple of flights seven days from now. I've received these annually for a few years but never tried to do a redemption. I'm using this trip for a mileage run to keep my platinum status for next year. Had to get special blessing from Hawaiian to book round trip Seattle-Honolulu same day with an hour and 15 minute layover. Have to cross fingers that the outbound flight to HNL is not delayed, or the purpose is defeated. Anyway, since I had flexibility in dates, I used Hawaiian site to find cheap fare dates, then used ExpertFlyer to check on first class availability. I found 10/31 had 7 open F seats outbound and 6 open inbound, so chose that date and booked the flights two weeks in advance. I had to wait a week, of course, to call HA to do the upgrade, but there were still 6 seats open each way, so the upgrade was easy. Perhaps other esteemed members here can advise as to a less torturous method to use these certificates?