To follow these instructions you must have a jailbroken device on iOS 4.1. You can learn how to jailbreak your device here.
Make sure you have installed OpenSSH and found your iPhone's IP Address.
Download either the 1080x800 patch files or the 960x720 patch files depending on your preference.
Double click the downloaded archive to extract it.
Launch Fugu from your applications folder. If you don't have it you can install it from here
Input your iPhone's IP Address into the Connect To: field and input root as the Username then click Connect.
Input alpine as the Password unless you have changed it as suggested here. Click Authenticate to continue.
Once logged into your device click the Go To... button on the toolbar.
Input /System/Library/CoreServices/SpringBoard.app/ into the entryfield, make sure Remotely is selected, and click the Go button.
Locate N88AP.plist in the right pane. Right click it and click Rename to add .bak to the end of the filename.
Drag the new N88AP.plist file from the archive you downloaded into the right pane.
Click the Go To... button on the toolbar.
Input /System/Library/PrivateFrameworks/Celestial.framework/N88/ into the entryfield, make sure Remotely is selected, and click the Go button.
Locate and rename AVCapture.plist, CameraRollValidator.plist, and MediaValidator.plist by adding .bak to the end of the filenames.
Drag the new AVCapture.plist, CameraRollValidator.plist, and MediaValidator.plist files from the archive you downloaded into the right pane.
Restart your iPhone 3GS to use the HD video features we just enabled!