I grew up with a nickname, and I prefer to be called as that. It is quite different from my first name. When I introduce myself I usually just use the nickname.
I plan to use my full name in publication, and I have published papers using the full name already.
My question is, how problematic is this choice? Should I try to change it? I would imagine someone not relating me to my papers/ not able to find me from the nickname.
I don't think this will be a problem. A large part of the research community will know you through your publications, and as long as the name is constant across those, you won't have a problem.
Amongst colleagues/researchers who also know you personally, this wouldn't be an issue since you can convey the dual name to them during interaction. For instance, your email signature could be something like Jay (John Doe). Similarly, if you use academic networking sites, you could either give the full name or the dual name (i.e. Jay (John Doe)).
The only case where this could potentially be a problem is, X talks about you to Y as 'Jay', and Y searches for 'Jay' (s)he may not come up with the right results. I think this is largely surmounted if you use Jay (John Doe) in written communication often enough, so that X passes that information along to Y. I have had colleagues tell me about a person, and also what name he publishes under, so that I can find him. If people hear it often enough, they make a strong association.
To be identifiable on publications you could give your name as
"John (Jay) Doe".
I've seen this several times, especially by people with Asian names working in English speaking countries where they use a different first name. (However, I do not know if these different first names are in any way official, but anyway…)
MathSciNet is able to collect your paper under a single profile (with a little help sometimes) and also a Google Scholar profile page can do the same thing.
How effective this choice is may depend on the characteristics of your name. How distinctive is your last name? If you have a very rare last name, going by two names is unlikely to confuse search results or people. Also, does your nickname start with the same initial as your full name?
Some colleagues I've known with very common last names make it a point to use the same form of their name everywhere, and create online resources (personal web page, LinkedIn, Google Scholar Profile, Orchid, etc.) that explicitly connect all their work together (especially when a journal or a citation format just uses initials + last name). (See, for instance, this question from an academic with a very common name.)
If you feel comfortable with your nickname in professional circumstances and it does not have negative connotations, I would encourage you to keep doing what you plan and set up some sort of web presence that explicitly makes the connection. Your CV should also reference your nickname, and including both in your email signature (as user153812 suggests) is a great idea.
EDIT: Given what you added about the previous papers being from an REU and being open to using your nickname professionally, you can also just opt to publish that way. It feels nice for even new colleagues to use the name I feel connected to. Your institution will not care. (Source: My institutions have not cared about my nickname. It's sometimes slightly annoying for people to look me up in the system for admin reimbursements, etc., which has my full legal name, but it's usually just a matter of writing on a form: "Nickname (Fullname) Lastname.")
On the one hand I don't think it will be a big problem either way. On the other hand, I see no good reason to stick with your legal name and a several good reasons to go with the nickname:
