I agree the use of "stateful UI" is ambiguous in general, but with respect to navigation I typically hear hierarchies referred to as stateless and activity stacks as stateful.

With a hierarchy like iOS every child is supposed to have exactly one parent so you only need to know the current page to know what the "back" button will do -- it will go up one level in the hierarchy to the page's parent regardless of how you arrived at the page.

With an activity stack like Android, it is not sufficient to know the current page, you must know how you got to that page because the "back" button refers to going back in the history.

Many websites support both -- the browser's back button is stateful and navigates your personal history, whereas on-page navigation like breadcrumbs are often stateless and do not depend on the particular path you took to get to the page. There are exceptions of course, many search interfaces are stateful in that drilling into an item and going back using the in-page navigation will return you to the prior query rather than the page's parent.