For example, something like this:
Array = {}
RemoteEvent.OnServerEvent:Connect(function(Player)
local Part = Instance.new("Part", workspace)
Array[Part] = Player
Part:Destroy()
end)
Will that leak memory? Will it automatically remove the index for that part once it detects that it's been removed? Or do I need to manually set it to nil when removing it?

2 comments
Depends if it has connections to it, however destroying disconnects all connections so this should not be an issue, you can read more about it here: http://devforum.roblox.com/t/90082
not really.. for as long as you can access the object and destroy it when unneeded, then you should be good...