By default in EF this join table won't appear as an entity instead you'll get a many to many relationship which will show up as two navigation properties
i.e.
Person.Stores
Store.People
If you want to build a many to many relationship without retrieving the entities then attaching stub entities is the best way.
var person = // you already have the person
var store = new Store{StoreID = 5} // you know the storeID
ctx.AttachTo("Stores", store);
ctx.AttachTo("People", person); // assuming the person isn't already attached
person.Stores.Add(store);
ctx.SaveChanges();
The only problem with this code is it will fail if the relationship already exists, so you need to be sure you are creating a new relationship
For more on using Stub entities like this check out my post.
Hope this helps.
Alex
Edit from OP:
Since I am using EF4, I used the following code to remove the string from the attach (thanks to tip 13 from the link).
var person = // you already have the person
var store = new Store{StoreID = 5} // you know the storeID
ctx.Stores.Attach(store);
person.Stores.Add(store);
ctx.SaveChanges();