After I've created a TRecordSymbol, how do I add a constructor and methods to it? I've tried using TMethodSymbol with little success, as I can't find a way to define the execution of the method.
Method symbols (like all TFuncSymbol) defer the execution to an interface (defined through the Executable property) for "normal" execution (ie. with a stack frame and parameters evaluated and pushed on the stack). "Magic" function symbols on the other hand require a dedicated expression class, and they take over the whole function call (so less overhead, but you've got to guard yourself against everything).
For samples, you can look at what the dwsMathComplex & 3d units do, they introduce records with custom methods.