You are already on the right track. By providing buildInputs you define build-time dependencies. stdenv sets these up in the environment for you. That’s why hello-world is available in your PATH and you can use the code from @abathur to get the actual store path. When Nix adds the package to the store after it has run the builder, it will essentially grep for store paths from the inputs in the output and adds those being found as runtime dependencies.
So you can add a runtime dependency by creating a file in the output containing the store path of the runtime dependency. This is the normal way to add a runtime dependency in a Nix build. The file could be a script, a binary, a config file or whatever you could imagine. Though a plain file only containing the store path is enough, it’s not very useful by itself of course.
That’s also why helpers like removeReferencesTo or nukeReferences exist to remove store path references in the output if there are somehow mentioned but actually not needed at runtime.
You already found nix-store --query --references. I also use --requisites to get the whole closure and --referrers to get all store paths depending on a given path. To dig deeper into large closures, I tend to use nix-tree these days for an interactive view of the dependency tree instead of the --graph or --tree options to nix-store.