max@op

Just to check if I understand what are you trying to do.
When you land on PageOne you have an regular index page, post titles with thumbnails and excerpts from all categories, and a menu to filter categories. When we click on category, that category posts are displayed. When we open post from PageOne specified category, next/previous links should consider only posts in that category cohosen on previous PageOne.
If so, for categores menu we can use wp_list_categories or calling custom nav menu in which ‘All’ link points to index or any custom page that will display all posts.
By clicking on category in one of this menus, WP queries posts and displays them trough category.php template, if we have one, else uses index.php. In permalink of that page is category info – can be cat ID, cat nicename, name or slug.
So i suppose that you use javascript not to filter posts, yet for an show/hide posts effect.
$_SERVER['HTTP_REFERER'] will return previous page link. We use it on a theme we’re just developing, for displaying different submenus on single page, depending on previous page. For example, if you open post from archive page, archive submenu will be displayed, if landed from tags page, there will be tag menu and so on.
So, maybe you could just trigger javascript on menu item click, and the previous – next links query using $_SERVER['HTTP_REFERER'] – previous page permalink.
When we click on category, WP reloads page, so maybe you could even if (is_category ()) page, trigger your script whenever category page loads.

Hi,
I use this code for single page with. Explanation is maybe a little big long, but it may help.

TERMS USED
category = any category
parent category = category with subcategories
child category = child (subcategory) of parent category

REMARKS
every category has parent category ID -> if category has no parent, parent ID = 0

PROCEDURE
1. get current post parent category ID
2. check parent category ID -> if is 0, it is category without children
3. get subcategories
4. check which of subcategories is current and add current-cat div to it
5. format data for output
6. echo subcategory list

FUNCTIONS
get_the_category () and get_category () returns stdClass Object for one, or array of stdClass Objects for many post categories and subcategories, depedens on ($args)

category stdClass Object contains next category objects
[term_id] => category ID
[name] => category name
[slug] => category slug
…
[description] => category description
…
[count] => No of posts in category
…
[category_parent] => parent category ID; if category is parent, ID = 0

VARIABLES
$postcat -> current post categories IDs
$cat -> post first category ID
$thiscat -> post first category objects
$parent -> post first category parent ID

<?php

	//* first let's get current post parent category ID

	$ID = $wp_query->posts[0]->ID; //* get current post ID
	$postcat = get_the_category($ID); //* based on post ID, get current post categories IDs -> WP function returns array of stdClass Objects, one stdClass Object for each category; if there is child - parent relationship, first it will return Objects for children categories and than for parents -> add "print_r ($postcat);" without quotation marks in next row to see content of array
	$cat = $postcat[0]->cat_ID; //* get first category ID from first Object in $postcat array (if post has children categories, it will get first child ID, else it will get first category ID)
	$thiscat = get_category ($cat); //* get array of category objects for $cat (current) category -> add "print_r ($thiscat);" without quotation marks in next row to see content of array
	$parent = $thiscat->category_parent; //* and extract parent category ID; if category has no parent category (and parent category has no parent), ID = 0

	//* now we have current category parent ID No, or if category has no children ID = 0
	//* let's check if we heave categroy with children categories or not

	if ($parent == 0) //* if parent ID = 0, it is category without chlidren

		{} //* do nothing 

	else { //* else, if it has children categories

		$subcategories = get_categories('child_of='.$parent); //* get array of children categories Objects and

		//* this next part is Marks (t31os) code from WP forum topic 'Showing subcategories of a parent page under subcategory'

		$items=''; //* create new ArrayObject and

			foreach($subcategories as $subcat) { //* foreach child category in array
				if($thiscat->term_id == $subcat->term_id) //* check if current category ID is same as child category ID
				$current = ' current-cat'; //* if true, add current-cat to li class
				else $current = ''; //* if not, add nothing

				$items .= '
				<li class="cat-item cat-item-'.$subcat->term_id.$current.'"> <!-- if is child current, add here .current-cat //-->
					<a href="'.get_category_link( $subcat->term_id ).'" title="'.$subcat->description.'">'.$subcat->name.' ('.$subcat->count.' posts)</a> <!-- link to -> category link, title -> category description, show -> category name and No of posts //-->
				</li>';
			}

		echo "<ul>$items</ul>";
	}
?>