Look in System Preferences > Displays. If an Arrangement tab is present then the Mac recognizes an external monitor and it's a TV problem.
If the tab is not present then the Mac doesn't know the monitor is there and is probably a cable problem.
Set the TV to the input you connected the HDMI cable to.
On your computer, if you open the Displays preferences and do not see an Arrangement tab (or there is an Arrangement tab that shows only a single monitor) then there is something physically wrong with your connection. Try clicking Detect Displays just to see if the computer can now sense the presence of the connection. Check your cables and make sure the mini-displayport plug is pushed firmly in so that essentially all the metal part disappears inside the socket. Mini-displayport plugs can be a little tricky in that you need to make sure the plug is fully seated in their socket.
If you do have an Arrangement tab, and it shows two screens, then click Gather Windows to bring the TV's Displays preferences on to your main screen if the TV is not yet showing an image. Set the proper resolution (probably 720p, 1080i, or 1080p). Set the refresh rate (probably 60Hz) if that preference is shown. You should see a picture at this point. I recommend turning off mirrored displays if it is enabled (more about this below).
You may have to play with the underscan/overscan settings on your TV and the displays prefs for the TV if the picture is too small or larger for the TV screen.
Also, you need to set your Sound preferences to output to the HDMI connection.
When using Lion, do not run in Lion full screen mode.
I'm hoping that it's a simple cable issue, but I'm dissapointed as this is a brand new cable that had good reviews from other Mac users. Providing I do find a cable that works, how do I know if I'm running Lion in full screen mode?
I would suggest that you get a mini display port to hdmi adapter and a hdmi cable instead of a all in one mini display to hdmi cable. That way you can test the hdmi cable with an other device like a xbox or a blue ray player.
I got my mini display to hdmi adapter at monoprice for about 5$ and an other 5$ for a hdmi cable and it works perfectly with my panasonic hdtv.
The only time I've ever run a cable as an "adapter" was for firewire400 to firewire800. In all other cases I've only used adapters. There's plenty of mini-displayport to HDMI adapters to choose from. I always recommened monoprice.com for stuff like this (cables and adapters):
As for lion full screen mode, I don't use lion, but I believe that is where an application takes over the entire main screen. The menu and dock are not shown unless you mouse over the area. And there is a pair of double arrows in the upper right of the menu bar to enter/exit full screen mode (reference). I believe if you have that enabled additional monitors are blanked out which is why I say don't use it when you want to use additional monitors.