It's not a problem for the server (and even then, it might be: what if the root handler simply sends to further sub-handlers after just chopping off part of the URL or query arguments? There isn't necessarily a central URL authority on the servier either), but generally is one for the client: in a truly RESTful system, the client knows one URL and one only (the service's root).
It also knows all the media types the service can return (which is why meaningful content-types, as those returned by Github, are great).
From this, it can traverse the service to the place it needs, and it may cache URLs along the way (for more efficient traversals later on) but those URLs may die altogether and require a re-traversal.
This scenario is built into the architectural style.
> In fact, you need to designate this someplace anyways, whether it's on your server (in the database or in some code), or on the client-side code.
If URLs are designated anywhere in the client-side code (outside of the root service URL and a URL cache, which is accumulated knowledge rather than built-in), it's not a RESTful service, it's RPC-over-HTTP.