I notice in your profile that you are using Windows XP. What are you using the sync your calendar/contacts, Outlook? What version, 2003, 2007? There is a section there to add holidays to the calendar, and once you do that and sync, they will be there.
I can check the exact location if necessary, just let me know what version, or you can check Outlook help and it will show you.
Once you sync the phone, they should show up in the calendar. They would be all day events, so they should be at the top of each day, when you look at the "day" screen. At least that is where all day events show up for me.
Looks like Outlook 2003 will only display holidays till 2007, not 2008. I guess Microsoft
wants people to buy Outlook 2007. 😟 According to their web site, Outlook 2007 will
display holidays till 2011.
This is a pretty roundabout method, but: I added US Holidays to my Google Calendar. Then I went to the settings for that calendar and downloaded its iCal file. Importing that into Outlook was a breeze, and the next sync put all the holidays (at least for the next few years!) onto my phone. 🙂 Does that help at all?