The solution should not require the user to click 'Save' to toggle its sensitivity, it should be insensitive from start.

#!/usr/bin/env python
from gi.repository import Gtk


class W(Gtk.Window):

    UI = """
    <menubar name="MainMenu">
        <menu action="MenuFile">
            <menuitem action="MenuNew" />
            <menuitem action="MenuSave" />
            <separator />
            <menuitem action="MenuQuit" />
        </menu>
    </menubar>
    """

    def __init__(self):

        super(W, self).__init__()
        self.set_default_size(300, 300)
        self.connect("destroy", Gtk.main_quit)

        box = Gtk.Box(orientation=Gtk.Orientation.VERTICAL)
        self.add(box)

        action_group = Gtk.ActionGroup("ui_actions")
        action_group.add_actions(
            [
                ('MenuFile', None, '_File'),
                ('MenuNew', Gtk.STOCK_NEW, '_New', None, 'Should enable save',
                 self._do_new),
                ('MenuSave', Gtk.STOCK_SAVE, '_Save', None,
                 'Only sensitive after new', self._do_save),
                ('MenuQuit', Gtk.STOCK_QUIT, '_Quit', None, 'Exits',
                 Gtk.main_quit)
            ]
        )

        uim = Gtk.UIManager()
        uim.add_ui_from_string(self.UI)
        self.add_accel_group(uim.get_accel_group())
        uim.insert_action_group(action_group)

        self._menu = uim.get_widget("/MainMenu")
        box.pack_start(self._menu, False, False, 0)

        #HERE'S WHERE I DON'T KNOW WHAT TO DO
        #How to append the widget corresponing ot 'MenuSave' into
        #self._sensitie_widgets
        self._sensitive_widgets = []
        self._set_sensitive_state(False)

        self.show_all()

    def _set_sensitive_state(self, val):
        """Does nothing now, because the GtkAction for 'MenuSave' has
        not been appended to self._set_sensitive_state"""

        for w in self._sensitive_widgets:
            w.set_sensitive(val)

    def _do_new(self, *args):
        """Callback should just invoke self._set_sensitive_state as below"""

        self._set_sensitive_state(True)

    def _do_save(self, widget):
        """This should only be possible after New has been pressed.
        Currently a failed attempt at tracing the way to access it."""
        def _do_trace(w):

            if hasattr(w, 'get_parent'):
                _do_trace(w.get_parent())

            else:
                print dir(w)
            print w

        _do_trace(widget)

if __name__ == "__main__":

    w = W()
    Gtk.main()

Solution 1:
w = [uim.get_widget('/MainMenu/MenuFile/MenuSave')]

solution 2:
Another solution: create and save Action objects: action_save = Gtk.Action('MenuSave', ...) w = [action_save]