(NB: I'm assuming a REST service that uses URIs to identify resources, I'm aware this isn't strictly a constraint of REST)
From my understanding of HATEOAS, a client shouldn't assume anything about the URI structure provided by a service except for the initial entry point (and instead should only use URIs given to it in a structured way by the server). Does this mean the client can only use URIs given to it by the latest request, or can the client keep track of URIs received in earlier requests from the same session? If the former, which REST constraint would the latter violate?
Two examples of keeping track of URIs:
I am not sure what you mean by your opening line:
NB: I'm assuming a REST service that uses URIs to identify resources, I'm aware this isn't strictly a constraint of REST
do you mean that hyperlinks don't have to be URIs? or that hyperlinks don't have to point to resources? The former is technically true but on the internet, URIs are the only form of hyperlink, so unless you're thinking about something Completly Different, then they are URIs. If you are saying REST doesn't require that URIs identify resources, then this is just wrong. That's exactly what they identify in a RESTful API. Always.
Anyway, onward to your question:
Does this mean the client can only use URIs given to it by the latest request, or can the client keep track of URIs received in earlier requests from the same session?
Yes, a client can cache previous responses. If they are 'fresh' (per the Expires or max-age headers) then the client can use them immediatly. If they are 'stale' (max-age/Expiry time exceeded) then the client MAY re-request the resource using a conditional request (e.g. If-Modified-Since), but it doesn't have to.
Neither of your examples constitute a REST violation. On the contrary, they are both wonderful examples of the simplicity of the system!