How should I get the Arduino to notify Via email or something?

All I came up with is that I should try pushing the email to a web server running a PHP script. Would that be the best solution?

That sounds like some type of klunky workaround. My arduino just sent me an email using the below code setup.

/*
SEND AN EMAIL WITH ARDUINO
9/23/11
This code was created by modifying the connect example from arduino.cc and with the help of the YABB forums and their very helpful members.
This code sends an email to any email address and then disconnects.  
*/

#include <SPI.h>
#include <Ethernet.h>

byte mac[] = { 0xDE, 0xAD, 0xBE, 0xEF, 0xFE, 0xED }; // Arduino's artificial mac address
byte ip[] = { 192, 168, 1, 102 }; // my ip
byte server[] = { xxx, yyy, zzz, aaa }; // my smtp.xxx.net server ip

Client client(server, 25);

void setup()
{
  Ethernet.begin(mac, ip);
 Serial.begin(9600);

 Serial.println("connecting...");
 
 if (client.connect()) {
                        Serial.println("connected");
   
                        client.println("HELO itismeletschat"); /* say hello (statement after helo is needed but irrelevant)*/

                        client.println("MAIL From: me@my-isp.net"); /* identify sender, this should be the same as the smtp server you are using */

                        client.println("RCPT To: you@your-isp.net"); /* identify recipient */

                        client.println("DATA"); 

                        client.println("To: you@your-isp.net"); /* identify recipient */
                        client.println("Subject: You Have Arduino Mail!!"); /* insert subject */

                        client.println("Please let me know it worked!!!"); /* insert body */
                        client.println("."); /* end email */
                 
                        client.println("QUIT"); /* terminate connection */
                        
                        client.println();
   
 } else {
   Serial.println("connection failed");
 }
}

void loop()
{
   delay(10000);
   if (!client.connected()) {
   Serial.println();
   Serial.println("disconnecting.");
   client.stop();
   for(;;)
     ;
 }
}