This seems pretty straightforward using cookies in straight HTML. In wordpress, how do I do this? AFAIK, wordpress only provides cookies functions for logging/logged in users. How about when I don't want the user to log in to show my greetings?
if you are not looking at coding it yourself then WP Greet Box(http://wordpress.org/extend/plugins/wp-greet-box/) could be used to achieve this. This plugin automatically loads a greeting message based on the referrer and it even allows you to customize the greetings, set time out to auto close the greeting etc.
The only problem I see(from your question) is that this plugin greets all visitors not just new. If the visitor closes it, it won't be shown again.
First time visitors based on cookies aren't reliable anyway, clear the cache and you become first time visitor again!