*NOTE*: Substrate requires you to have "root" access on your device. Substrate may be incompatible with your device (such as missing symbols), but will attempt to detect this. There is also an irritation with many HTC devices; Substrate has a new workaround in it as of June 1st (0.9.4008) that should allow it to work on these systems.
(June 2nd now: it seems a small number of Samsung devices have a similar issue, and Substrate correctly detects that it canot use the same workaround; I will work on a new solution, likely one that solves both of these use cases at the same time. There is no harm in running Substrate and seeing if the workaround is possible: that's detected.)
Substrate is a platform for customizing software. Due to limitations of the Google Play Store it must be installed separately, but its primary purpose is to support other products: users should not expect Substrate itself to do anything interesting. Instead, it should be thought of as enabling your device to support other things you may install.
Products that use Substrate are able to modify any other program, whether it came with your phone or was installed later, or whether it was developed by Google or by a third-party developer. These kinds of changes carry an inherent risk: changes to the underlying software being modified may break the modifications ("extensions") you install.
*IMPORTANT*: Substrate for Android is new. While I've spent a bunch of time testing it on a bunch of devices with many versions of Android, there is always the possibility that there's something unique to your setup that causes an incompatibility. If possible, I'd recommend having a backup of your device handy; I'd also recommend being setup with a recovery mode image that allows you to easily delete Substrate. For more information, see this FAQ item.
Users should keep in mind that Substrate includes a safety feature: by holding down the volume-up button on your device you can disable Substrate while it is attempting to load these modifications (such as while it is turning on and starting); this will give you an opportunity to use Google Play to uninstall things that might be broken.
Substrate has been tested fairly extensively. It is designed to work on Android versions 2.3 or above, but will work on any "equivalent" versions (systems like CyanogenMod or the Kindle Fire use their own versioning schemes). It is supported on devices that use either ARM or Intel CPUs and works on "strange" devices (including Google Glass).
While Substrate support for Android is very new, Substrate was first released in 2008 for Apple's iPhone and is now being used by tens of millions of devices worldwide. Many people know it as "MobileSubstrate", how it is usually distributed for the iPhone, iPad, and iPod Touch via Cydia, the alternative to the App Store for "jailbroken" devices.
If you are a developer, you can learn more about how to work with Substrate at http://www.cydiasubstrate.com/. There, you will be able to find documentation, tools, and examples. Substrate for Android also shares many development concepts and APIs with Substrate for other platforms, so tutorials from third-party websites may help.
(Users of Substrate on iOS may remember that there is a more general "Safe Mode" feature that will catch crashes, allowing for a more intuitive response to failures. This will be implemented in an upcoming version of Substrate for Android, but please remember: you can always use the "volume up to disable" feature to skip bad extensions.)
(Substrate requires the ACCESS_SUPERUSER permission, and during its installation it will add a few files to your device. No files will be modified or overwritten: only a few new files--all symbolic links, taking up virtually no space--are added. Substrate only requires root during installation and to help it restart your device to use new extensions.)
* fix decoder bug inside ARM emulator
* support Genymotion Intel emulator
* add symbol names for Moto X
v0.9.4010: critical Android 4.3 fix, avoid old Superuser bug
^^ must install before Android 4.3 OTA!
v0.9.4009: work around Xposed bug, 4.2 fix, better errors
v0.9.4008: HTC linker path patch, limit symbol exports
v0.9.4007: RAZR i 4.1.2, detect HTC override, avoid ps
v0.9.4005: incompatibility detector, avoid mount/ln/mkdir
v0.9.4004: Holo, Script Failure, detect physical /vendor