Your easycfm link seems a good start.
It really depends on your RDBMS as well, since mySQL supports functions that easily allow for you to capture just the data you want, while MSSQL requires you to just about pull back the whole recordset and then selectively retrieve a subset (the size of the pagination) from it.
For example, MSSQL 2012 finally introduced the standards-compliant FETCH and OFFSET keywords, so you could do something like
ORDER BY primaryKey
OFFSET 5 ROWS
FETCH NEXT 5 ROW ONLY
Since ordering by primaryKey (assume 1, 2, 3, 4, etc) This would return the record starting at 6 and give you 5 records worth (to ID 10).
That way CF can just send the RDBMS system the offset (what page you're on) and the fetch size (the amount of records per page). Then it's just a case of math to determine the text of "Next X records", etc.
This is how i make the Next and previous link.
== At the top of the page ==
<cfparam name="URL.StartRow" default="1">
<cfset NextRow = URL.StartRow + 25 />
<cfset PreviousRow = URL.StartRow - 25 />
<cfif PreviousRow LTE 0>
<cfset PreviousRow = 1 />
== Next and previous links ==
<cfif NextRow LTE QueryName.RecordCount >
<a href="#CGI.SCRIPT_NAME#?StartRow=#NextRow#">Next page</a>
<cfif PreviousRow LT URL.StartRow>
== Query results ==
<cfoutput query="QueryName" startrow="#URL.StartRow#" maxrows="25">
#Your output goes here#