1.I have two pages, Page 1 and Page 2, dropped Advanced Articles on each of page.
2.In Page 1, through Manage Categories i created a catagory "Sports", checked on for Sharing acorss modules and selected All users Roles to view this category.
3.Same way in Page 2 i created a category "Career" and shared it with same configuration as that given in point 2.
4.On Page 1 when i do Add/Edit Article it does not show the "Career" category for selection. Same happens if i add/Edit article when on Page2, it does not show the "Sports" Category.

If i share a category in one module, it should be available for selection in Add/Edit Article page on other existing modules. Correct?

Yes.

These categories dont get shared across the modules even after marking them as shared.
It does not appear in either of the modules Add/Edit Article screen for selection.

Did you assign the proper permission to the users to access the category?

Yes i had assigned the permission to All Users and Administrator