According to the PM you sent me you're using HostGator as your web hosting provider, which appears to be running Apache, so that should be fine. However, for the first URL structure option to work the directive "AllowOverride All" must be enabled in your virtual host, otherwise the .htaccess file won't work (see the documentation about htacess linked in that first option). Whether that directive is enabled or not is a question you need to take up with your provider.
Also, as mentioned in the same documentation, you may need to uncomment the directive "RewriteBase /" in your .htaccess file, depending on the webserver configuration.