If you're looking to store configuration information - app.config or a settings file is probably the way to go.
If you are storing user data - you should really allow the user to control where it is saved - and prefer the \User\Username folder on the machine.
As for what format to store it in ... you can certainly use something like SQLLite - but there's nothing wrong with XML either, if you're not storing true binary data. .NET offers a number of APIs to transform object graphs into XML representations - which you may want to look into.
If you don't want to store anything on the local user's machine, you probably want a network database - or a webservice - to which you upload the users data. Just make sure your users understand this - many don't like their private data being sent somewhere on the web without their consent.
You really don't want to go about modifying the executable file. Many virus scanners quarantine executables that are constantly changing in content or size - as a way to proactively prevent viruses and malware from infecting the machine. You don't want to go there.