Since launchd starts and stops the screen sharing process, you can create a new launchd job that uses a KeepAlive dictionary with an OtherJobEnabled clause to tie your warning tool to the launchd label com.apple.ScreenSharing.server
When ScreenSharing starts, your job will also be started by launchd. (or vice versa if you prefer)
The system job you wish to key is /System/Library/LaunchAgents/com.apple.ScreenSharing.plist
Your plist should go in ~/Library/LaunchAgents
or /Library/LaunchAgents
depending if you only want one user warned, or all users warned. I would also set LimitLoadToSessionType to Aqua.
As mentioned by @jm666 - Growl can make some very pretty notifications with a lot of control and transparency, overlay etc..
growlnotify --appIcon Screen\ Sharing "Screen Sharing" -m "is now active - click to dismiss" -s
You could get very fancy with a shell script to determine the source IP, date and time, log the connection or do all sorts of fun things since launchd has great support for shell scripts as well as full applications.
A quick and dirty Apple Script might be good for testing to be sure launchd is working and you can always polish the presentation later.
osascript -e 'tell application "System Events" to display alert "Incoming VNC session started" as warning buttons {"Cancel", "OK"} default button "OK" cancel button "Cancel" message "Screen Sharing is now active and someone can see and control this Mac until the menu bar icon of \"binoculars inside a monitor\" turns back into binoculars alone. "'
See these links for more info on launchd and AppleScript dialog for reference.