I'm building a Slack slash command that looks like the following
/shoutout [@recipient with message]
This will trigger a POST to my server with both the sender and recipient's user IDs. However, I need their full names. I'd like to send requests to the Slack API for their names, which seems possible via making GETs to https://slack.com/api/users.info with user IDs.
The problem I have with understanding how to do this is about the token requirement. I know how to do this with my Workspace (just send my workspace's OAuth token as part of the request), but how do will this work with other workspaces that install my app? In other words, how do I get a valid OAuth token for other workspaces that install my app? Am I approaching this incorrectly?
You are on the right path. You indeed need an individual token for every Slack workspace that your app is supposed to work on.
To get it your app has to be installed to each workspace once and your app needs to catch and store the token that will be created during the installation process. The installation process is a standard Oauth2.0 flow and usually managed by an external website that negotiated the OAuth flow with Slack for the workspace. That webpage usually has a "Add to Slack" button, which will start the installation process.
To make that happen you need to do the following:
You need to create a Slack app to get a Client ID and Client Secret
Activate distribution for your Slack app on your apps's the admin page
Create a web page that handle's the Oauth flow
Here is a more detailed description of the Oauth flow for Slack.
Here is more detailed info about the Slack Button.
Finally, here is an example PHP script for installing a Slack app to a workspace.