This can be slightly confusing, so I'm going to clarify some more.
If you're using glBindAttribLocation then you must make your glBindAttribLocation calls before linking. In the old days (i.e. before GL_ARB_explicit_attrib_location) I liked to specify a struct describing the attribs, pass an array of those structs to my shader creation function, and loop through that array binding my locations before making my glLinkProgram call. I expect that's probably the way most people do it.
In this case if you've already linked the program, you don't need to worry too much - you can just make your glBindAttribLocation calls and then call glLinkProgram again. This is obviously not ideal - you really should just link once (for no reason other than it makes program startup faster) so view it as a "get out of jail" card that you can use pending a redesign rather than as a permanent working solution.
If you're using glGetAttribLocation you must make your glGetAttribLocation calls after linking. The same struct trick I mention previously could be used here, but in general I never liked using this call as I always wanted the same attribs in the same locations across different program objects (so that I could change programs without having to issue a new set of glVertexAttribPointer calls, for example).
If you're using explicit attrib locations then in theory you don't need to do anything. You specify an attrib location in your shader, you use that same location in your C/C++ code. You may if you wish query the attrib locations using glGetAttribLocation (after linking) if you want to generalise things a little more, but this never really bothered me as I see a danger in trying to generalise too much.