Here is a coarse overview which steps I regard as essential for this kind of analysis. The actual way to do this best depends on many factors like type of data (Illumina, Solid, 454, paired end single end), read length, preferred programming language or toolbox (aka. R, Perl, Galaxy) the grouping of your data into samples, number of replicates, the alignment tools, etc. which you didn't specify.
for this you will need:
- The full genome sequence of your organism (as a FASTA file)
- All annotated regions of the genome (including known annotated ncRNAs) (best in a GFF file)
- your reads
With that:
- Filter reads
- Align reads against the whole reference genome
Find regions of high coverage (this is the hard part, the question is how to define it, e.g by cutoff or by significance using replicates)
Edit: An idea to calibrate the coverage cutoff required might be to look at the coverage of know RNA-genes.
Remove regions that overlap with annotated exons (or in addition with known RNA genes)
Edit: This step could be optional, for the cases GWW mentions, but that will most likely yield almost all transcripts.
Keep regions that are in introns or intergenic regions of the genome and have suitable distance to coding regions.
Some steps of the pipeline and possible follow up analyses are also outlined here: Identified Potential Non-Coding Rna, And Then?
Also have a look at the rna-seq questions here: https://www.biostars.org/t/rna-seq
That way you will only get regions that are new, and far enough away from exons.
This is not too difficult to code in for example R or in a local Galaxy install, but I am not sure how much help it is, depends on which of these steps you can perform yourself. So I would suggest that you get some local support from a (bio)informatics person on-site.
What type of RNA-seq data, precisely, do you have?