Visio has a feature which allows third-party solutions to store it's custom data in Visio files as XML fragments. It might be useful if you don't want to litter document or shapes shapesheet(s) with your data. Also it has an advantage that setting it, unlike setting cells in shapesheet, does not trigger undo/redo, so user's work is not interfered.
Working with solution XML elements might require a bit work, here is a short code fragment how to deal with that in C#. The key point is that you need to create your own namespace in the XML, and then all your data should go there. The sample assumes that you want to store some "settings" in the solution xml element.