Install this plugin alongside check_ping, select a diverse set of pingable servers "on the Internet", put their IPs into /var/tmp/check_internet (one per line), make that file writable for your Nagios process, and you're all set to monitor "the Internet connection". check_internet will check up to three hosts per invocation, and report CRITICAL if all three have been found to be unreachable.
Unlike using check_ping on the servers directly, this solution will not raise alerts for a single unreachable host; and unlike check_ping'ing some network device halfway between your uplink and the actual Internet, it does not require that you (obtain and) maintain information about your provider's network in your Nagios.
Note that the number of target hosts must be at least three (so that check_internet can check three different hosts in one go), and should probably not be larger than 3 times max_check_attempts (so that all hosts have been checked and found unreachable when the service enters the HARD state).
check_internet can also double as the host check for your "the Internet" pseudo host. In that case, it should not output performance data (I found that that confuses n2rrd). v1.2 will only output performance data if the "-p" option is given.
-- Setting enable_environment_macros to 0 broke the autodetection of whether check_internet is called as host or service check, so I made it an explicit option; call it as "check_internet -p" to have perfdata.
-- The original plugin lost about one site per month from the /var/tmp file for me. Rather than implementing full file locking, I added code to have it reinitialized from a master copy every so often (every 14 days).
-- Fixed the PTR checking so that servers that lack a PTR RR do not lose their (initial) FQDN.